SOLUTION - iPhone 3GS (iOS 6.1.3) AT&T
This worked on my iPhone 3GS running iOS 6.1.3 on the AT&T network...My iPhone is not jailbroken or unlocked, so I cannot be sure about those devices!
STEP 1: WARNING: BACK UP YOUR NOTES AS THEY WILL BE DELETED FROM YOUR iPHONE
STEP 2: Go to Settings → Mail, Contacts, Calendars.
STEP 3: Go into EACH email account individually and slide OFF notes! (I know this will work for Gmail, but I am not sure about other email account types. You will have to go into them and see if there is a "slider" for notes. My email is a Gmail account.)
That's it. Let me know if it worked for you! My fiancé has a iPhone 5C (iOS 7) so if you are having this same issue on a 5C running iOS 7 I can mess around with hers and try to figure it out for you...Good luck fellow iPeople!