Is there any reason a really old iPhone 4 would fail to backup notes?
Notes are still carried over if you have a Microsoft Exchange account and MS Outlook, though you can no longer back them up to the iCloud.  Another option is to backup the phone into iTunes on the local machine and restore it back to the new phone.

I can't really tell which it is that happened because I did both things.  If anybody knows what happened, please be sure to post it here.