HTC Sensation (Z710e) Android 4.0.3, no mods, not rooted. Having 347MB of free space on internal storage and 185MB RAM.
Updated Evernote today and it stopped syncing saying "Insufficient memory space" at the bottom inside the app
and "Insufficient memory space - There is not enough space on the memory to sync" in the notification area.
Tried reinstalling/rebooting - same result.