You have to set that notes save to your me.com address on both of the devices, not to "On my Mac" or "your iphone's name" account".
1.) In mail, under Composing tab, make sure you have your @me.com address under "create notes in". This will make every note that you create go directly to iCloud. You should see every note that you create now also on
http://www.icloud.com and vice versa.
If seeing notes in Mail me.com inbox is your preference, check "show notes in inbox" under "account info"->"Mailbox behaviours" for your me.com address.
2.) On iOS, there is an option in which account you create your notes. You are probably making them on your iPhone, not me.com address. Make sure that is your me.com address account as well. Not really sure how you check in which account you are making the note in.
Both in Lion and in iOS5 yo should have notes synching over icloud enabled (I'm sure you have that already).
What I did was when I had 1.) working, I synced all notes from my iOS device to my Mac via iTunes. When they showed up in Mail, I cut&pasted them to my me.com inbox (so they were on iCloud at this point). Then I deleted every single note from my iOS device (also turn off notes synching in iTunes at this point!) and set up iCloud syncing and then every note got pushed to it. And then "it just works" from here on.
Make sure you have your notes backed up one way or the other. I'm not responsible if you lose anything.
