New Notes Will Not Sync From Mac to iPhone or iCloud
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: 


open the notes app 
click on notes in the notes.app menubar
set default account to "iCloud". (You can also click help and search for default account to find the option.)