I just did a test, to confirm that it does work for me.
I deleted all songs from my 2G shuffle. Then, I manually added ONE song. I picked a song that I knew only had one version in my iTunes library, not a song with more than one recording. I noted the play count for that song, in my main library and on the shuffle (as shown on iTunes window). I ejected the shuffle. I played the one song on the shuffle until it finished and started to play for a second time. I paused playback, and reconnected the shuffle.
When the shuffle appeared back in iTunes, the playcount (both in the main library and on the shuffle) had advanced by 1.
Would it be possible to do the same test with your shuffle and your iTunes installation?