I have an iPhone 3G S with iOS4. I use MobileMe for my Mac Mail and iPhone Mail. I have been having the same problems with Mail on the iPhone after installing iOS4. I contacted Apple Support, and they had me re-install a fresh copy of iOS4 on my iPhone 3G S, then restore my user data from backup. This temporarily got rid of the problems; but as was my experience and plenty of other users' experiences, these sorts of remedies are unfortunately temporary. This morning, when I checked my Mail on my iPhone, all the bugs came back.
NOTE: These bugs only seem to affect my iPhone 3G S, but my wife's iPhone 3G has none of the bugs. Her iPhone 3G has unfortunately slowed down drastically in all functions since installing iOS4, however.
Here are the bugs that still recur in iOS4 Mail on my iPhone 3G S;
1) Mail messages marked as unread (blue dot) on the iPhone remain marked as unread (blue dot remains) after being read on either iPhone or Mac. (This problem is present only on the iPhone Mail; not Mac Mail or MobileMe Mail on the Mac.)
2) Sometimes a red badge icon displays a number of unread messages, but the badge and number remain, even after the messages have been read. (This problem is present only on the iPhone Mail; not Mac Mail or MobileMe Mail on the Mac.)
3) Messages appear with 'no sender' and 'no subject' and are dated 12/31/69. They cannot be deleted manually, because when the 'Edit' button is tapped on the iPhone, no circle appears next to the message to delete it. (This problem is present only on the iPhone Mail; not Mac Mail or MobileMe Mail on the Mac.)
4) Some normal messages that can be read also cannot be deleted manually, because when the 'Edit' button is tapped on the iPhone, no circle appears next to the message to delete it. (This problem is present only on the iPhone Mail; not Mac Mail or MobileMe Mail on the Mac.)
Most of these issues resolve on their own, but this often takes quite a while. Here is another post on the Apple forum with customers experiencing the same problems:
http://discussions.info.apple.com/thread.jspa?threadID=2472155&tstart=0&start=30