If I create a new note on my iMac (OS X 10.8 Mountain Lion), it will not appear on either iCloud or my iPhone 5 (updated with the latest iOS). However, I CAN edit existing notes and those changes do sync to the cloud and to my iPhone. Very Annoying. I can create a new note on either cloud or iPhone and it all syncs. I just CANNOT create a new note on the Mac and have it sync to the cloud.
Also, in case you wonder, I do not have this problem with either calendar entries or contacts. I am able to create new contacts and events on my Mac and they all sync to the cloud and my iPhone.
Best Answer
I had the same problem, and found out how to solve it. The default account for notes on the mac is "On My Mac" you want it to be "iCloud".
How to make that happen: