On your iphone, make sure your default notes are set to MobileMe, not your local iphone. You are probably creating new notes locally on your phone. I thought the setting was in Settings > Notes, but for some reason I don't see it there right now, just the 3 font choices.
Also, whenever I restart my phone, I have to turn Note syncing off and then back on again for them to sync up. I haven't figured out why. My MBP and ipad 2 sync up fine.