Syncing old phone with new computer - what is this message?
First things first: back up your phone data.

Then:


Open the Notes app on your "new Mac" (I assume you're using Mountain Lion).
In the menu bar, select Notes.
In the drop down pick list, select Default Account, and make sure iCloud is ticked.


If iCloud doesn't show up, click on Accounts and add it first.