I had problems with this too. I think i found the solution. The new os 5 and lion create different accounts for notes, an "icloud note" and a "on my iphone" note, both on the iphone. Also, an" icloud" note along with an "on my mac" note account on your mac. If you are the administrator you may not see the "icloud" note, your icloud email address will be displayed.
Now, to sync notes you have to use the icloud / icloud email address note. The way you do this is, on the iphone go into settings > notes and pick the icloud as the defaut note setting (or if icloud isnt a choice pick your icloud email address as the default note setting) You can also choose the icloud note right from notes, when you open notes there is a button in the upper left corner that says "accounts." you can then pick the icloud account at the time you are making the note. When you create a note, the note is sent to your email address. On the mac, in the notes section of your email screen, you will see: notes >on my mac and icloud(or your icloud email address will be displayed) You can view your synced notes there.
The problem with this is it syncs the note as an email and your inbox gets full with all your notes, if you delete the note-email frome your inbox the note gets deleted from all devices too. The work around is to go into your mail and open preferences>accounts>mail box behaviors and uncheck the "show notes in inbox." once you do this your notes sync between all devices that are set up this way. If you make changes to the note, the note changes on all devices and the notes do not clutter your inbox.
took me a week to figure this out. I was bumbed when note syncing wasn't as smooth as on mobile me, everything else is syncing well. With notes, it just didn't work. Hope this helps