[jimscard]

In order for Exchange Direct Push to work, both the phone & the server have to be set up correctly. You mention that you used to have your server sync'ing with a different phone - you might check with your Exchange administrators to make sure that they're not blocking the new one.