Hmm, I can't reproduce this here.
I suspect this might be some Qt version issue or modified theme svg issue.

What's the Qt version? (run "qmake -version" in console to get it. or paste here output of "ldd `which kmines`")

Would be cool if others would try to reproduce this on non-Ubuntu distributions.

I can reproduce this on my self compiled build, note that the bug is not that well documented as Steve says and the red/blue dots are not what the user sees, they are painted over the image to show the bogus squares.

What i do:
 * Open kmines
 * Maximize it
 * Check the top row is completely straight (it is)
 * Click anywhere in the board
 * Check the top row is completely straight (it is not)

This is even more obvious using the gardens of danger theme as the top row becomes alternate white/blue.

BUT if i change the window of the size the artifacts disappear so i'm not sure this is a kmines bug and might be a Qt/X/driver one

It might be the very old QGraphicsView-with-svg-items bug that one can easily see in KBlocks?
To see it clearly in KBlocks, launch the game. Then to make things easier to visualize, get the Black and white theme using KNS (in the Themes window). Now while playing, resize the game screen freely. You will see the strange patterns of drawing for individual elements, only at certain screen sizes. They are all the same element, so there is a rounding bug there when painting.
This seems to be a Qt painting bug, imo. I first demonstrated it close to 2 years ago, and had a test movie (with QGraphicSvgItems and QGraphicPixmapItems) available to the QGV developers at that time. Notice that the location of the screen redraw does not correspond to where the mines are.

Don't think so, my comment was not very correct either, i mean that if i make the window small and then big again (to the previos size that was causing artifacts) artifacts are not there anymore, so doesn't seem what you are describing

(In reply to comment #2)
> note that the bug is not that well documented as Steve says

thanks...

> and the red/blue dots are not what the user sees,
> they are painted over the image to show the bogus squares.

I had already said it clearly...

> What i do:
>  * Open kmines
>  * Maximize it

It happen also with a normal windows (not maximized) but not all the time:
If it does not happen you can move the mouse on the "New" button, left click on it and try again...

> BUT if i change the window of the size the artifacts disappear so i'm not sure
> this is a kmines bug and might be a Qt/X/driver one

This is true, if I resize the windows the artifacts disappear.

(In reply to comment #1)

> What's the Qt version? (run "qmake -version" in console to get it. or paste
> here output of "ldd `which kmines`")

andrea@kubra:~$ qmake -version
Qmake version: 1.07a (Qt 3.3.8b)
Qmake is free software from Trolltech ASA.

andrea@kubra:~$ qmake-qt4 -version
QMake version 2.01a
Using Qt version 4.5.0 in /usr/lib

andrea@kubra:~$ ldd `which kmines`
        linux-gate.so.1 => (0x004a6000)
        libkdegames.so.5 => /usr/lib/libkdegames.so.5 (0x00986000)
        libknewstuff2.so.4 => /usr/lib/libknewstuff2.so.4 (0x00906000)
        libQtXml.so.4 => /usr/lib/libQtXml.so.4 (0x00b84000)
        libQtNetwork.so.4 => /usr/lib/libQtNetwork.so.4 (0x00110000)
        libkdeui.so.5 => /usr/lib/libkdeui.so.5 (0x004a7000)
        libkdecore.so.5 => /usr/lib/libkdecore.so.5 (0x00bc9000)
        libQtDBus.so.4 => /usr/lib/libQtDBus.so.4 (0x0022c000)
        libQtCore.so.4 => /usr/lib/libQtCore.so.4 (0x00dfb000)
        libQtSvg.so.4 => /usr/lib/libQtSvg.so.4 (0x00ae6000)
        libQtGui.so.4 => /usr/lib/libQtGui.so.4 (0x071bf000)
        libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0x0037d000)
        libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0x002a1000)
        libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x002c7000)
        libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0x08ad1000)
        libkio.so.5 => /usr/lib/libkio.so.5 (0x05a6a000)
        libkdnssd.so.4 => /usr/lib/libkdnssd.so.4 (0x002d6000)
        libz.so.1 => /lib/libz.so.1 (0x002f8000)
        libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0 (0x0030e000)
        libSM.so.6 => /usr/lib/libSM.so.6 (0x0086c000)
        libICE.so.6 => /usr/lib/libICE.so.6 (0x00327000)
        libX11.so.6 => /usr/lib/libX11.so.6 (0x09c75000)
        libXext.so.6 => /usr/lib/libXext.so.6 (0x0033f000)
        libXft.so.2 => /usr/lib/libXft.so.2 (0x008a6000)
        libXau.so.6 => /usr/lib/libXau.so.6 (0x00b3b000)
        libXdmcp.so.6 => /usr/lib/libXdmcp.so.6 (0x0034f000)
        libXtst.so.6 => /usr/lib/libXtst.so.6 (0x00354000)
        libXcursor.so.1 => /usr/lib/libXcursor.so.1 (0x0046c000)
        libXfixes.so.3 => /usr/lib/libXfixes.so.3 (0x0035a000)
        libXrender.so.1 => /usr/lib/libXrender.so.1 (0x00475000)
        libbz2.so.1.0 => /lib/libbz2.so.1.0 (0x0088b000)
        libresolv.so.2 => /lib/tls/i686/cmov/libresolv.so.2 (0x0047f000)
        libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0x00495000)
        libgthread-2.0.so.0 => /usr/lib/libgthread-2.0.so.0 (0x00499000)
        librt.so.1 => /lib/tls/i686/cmov/librt.so.1 (0x00823000)
        libglib-2.0.so.0 => /usr/lib/libglib-2.0.so.0 (0x05d0a000)
        libaudio.so.2 => /usr/lib/libaudio.so.2 (0x0082c000)
        libpng12.so.0 => /usr/lib/libpng12.so.0 (0x00844000)
        libfreetype.so.6 => /usr/lib/libfreetype.so.6 (0x069ae000)
        libgobject-2.0.so.0 => /usr/lib/libgobject-2.0.so.0 (0x008ba000)
        libfontconfig.so.1 => /usr/lib/libfontconfig.so.1 (0x00a86000)
        /lib/ld-linux.so.2 (0x0035f000)
        libstreamanalyzer.so.0 => /usr/lib/libstreamanalyzer.so.0 (0x067ee000)
        libstreams.so.0 => /usr/lib/libstreams.so.0 (0x00b3f000)
        libsolid.so.4 => /usr/lib/libsolid.so.4 (0x07d33000)
        libacl.so.1 => /lib/libacl.so.1 (0x00875000)
        libattr.so.1 => /lib/libattr.so.1 (0x0049f000)
        libuuid.so.1 => /lib/libuuid.so.1 (0x0087d000)
        libxcb.so.1 => /usr/lib/libxcb.so.1 (0x00964000)
        libpcre.so.3 => /lib/libpcre.so.3 (0x00ab3000)
        libXt.so.6 => /usr/lib/libXt.so.6 (0x02b64000)
        libexpat.so.1 => /usr/lib/libexpat.so.1 (0x03afc000)
        libxml2.so.2 => /usr/lib/libxml2.so.2 (0x06c6c000)

With Albert's instructions I too am able to reproduce.

A similar issue can be seen with the "Gardens of Danger" theme when middle clicking and dragging around on the game area.

(In reply to comment #5)
> It happen also with a normal windows (not maximized)

screenshot in my bug report in launchpad
are taken on a non maximized kmines...

I did some additional debugging, and I can reproduce it (compiled by source,
qt-copy 4.5.1) as well, but only with Gardens of Danger. It is a different
redraw issue, but also one that is most likely a Qt-QGV regression, as there
was no change in KMines code that could justify it. 
No matter what you click, the clicked item is redrawn with an offset in the
scaling, only at certain window sizes. It is a graphics bug: it does not matter
what is in the underlying square (a mine or not).

(In reply to comment #9)
> It is a graphics bug: it does not matter
> what is in the underlying square (a mine or not).

may be, but in my case I never seen
a mine under a "normal" square.

ok, I try to be more precise:

when it happen each mine is under a strange square
and not all strange square contain a mine.

so, I see a relation between the "strange"
square and the underlying mine...

I can't reproduce this with Qt-4.6 now.

Please test against KDE-4.4.

This must have been a Qt regression indeed.