I just needed to delete the IMAP account and re-create it.
Something must have changed with the way IMAP messages are handled WRT the client for the IMAP client to get so confused. No clue, but consistent behavior from 3 different Nokia E62's that were great with 4.0.x but choked with 4.5.0.
I'm guessing this is related to my other thread about Mail For Exchange getting confused also (
http://www.zimbra.com/forums/showthread.php?t=6348).
Anyway, all is good!