For someone that prides himself on security, it is rather embarrassing to get hacked. I currently don't know how they got in, or exactly what they have done. I have changed my passwords and security questions though.
So far, I know that my account was accessed from Poland (188.8.131.52) with last access at 8:49 am today. It only appears to have been accessed via a browser, and there don't seem to be any extra filters (forwarding) setup. I do know that it appears everyone in my address book has been sent a link, although the link I can see that was sent (thanks to a bounce back) doesn't appear to work. They also deleted everything from my sent box and trash, which is probably what annoys me the most. I don't know if anything else has been deleted.
The most likely method they got in by was from an attack on another site, that revealed my password from when I used the same password in more than one place. As I no longer do this, I've been slowly changing my passwords to all be unique, however I should have changed my gmail one along time ago.
So 2 morals to this story. Even security conscience people can get hacked. And backup your data from the cloud if you wish to avoid loosing anything. I'm now in the process of setting up version controlled backups of my gmail data.