You are a star. It worked. Kind of annoying that this is the solution though as I have always used my gmail account (which my iTunes was signed in with) for iTunes purchases, and my mobile me (which my phone was signed in with) for syncing calendars, bookmarks etc. I guess this means that, if I have to choose one to have them both signed in with, I will lose functionality of the other?
Either way, thanks for helping me out, was losing hope! Very grateful.
miKe.Tomb: glad you found your solution too! Thanks for sharing!
p.s., thanks to everyone else who tried to help. much appreciated.
I am logged in to my MobileMe/iCloud @me.com account for iCloud services (mail, contacts, calender, etc.) and my old gmail AppleID for iTunes (music and app purchases) simultaneously. So far everything works as it did before iCloud. I make iTunes purchases under my old AppleID and everything else is synced just like it was with MobileMe.