I had the same problem. What you want to do is to go to Mail preferences --> accounts --> edit accounts --> special mailboxes, and then click on "move deleted messages to a seperate folder" (or something to that effect, I dont remember it word for word)