texasag90, berrywoes states that he has already tried that.
Fear not though, I had the same problem as you do. I can't remember exactly how I did it, but I can offer a clue. With the new firmware, the default accounts on the phone changed. Assuming you're like me and just have a T-Mobile BB plan and no BES, you'll have
, Web Client, and Desktop. Go to your messages, then Options, then Email Reconciliation. Select the first option (Message Services) then click it and choose Change Option. This is where my memory gets foggy... Select the one like
and make sure it says "Delete On: Mailbox & Handheld." Hopefully that should work.