Why did my iPhone Notes stop syncing with Gmail?
The problem is that Google's implementation of IMAP isn't really 100% IMAP, so it doesn't really support notes. I've been trying to get it to work for quite a while which ended up with me losing all my notes (although they may still be in the Google Mail archive somewhere).

I've actually given up trying to sync notes between my Mac/iPhone/Google and have gone for the Plain Text app which stores the notes on DropBox, this seems to work so much better. Now if only I could delete the Notes app from my iPhone.