Maybe last.fm has trouble with timezones or something.
Yes, that appears to be the case. I've checked quodlibet's plugin which has always submitted the correct time for me, and that uses time.gmtime() instead of time.localtime(). I've changed that in scrobbler.py.