Just got the Fascinate today and I am trying to set it up to work with Exchange. I have followed all the instructions from my IT department but am still having problems.
Download Nitrodesk Touchdown from the market and see if you still have issues. Sometimes the stock app just will not work, and Touchdown always comes to the rescue.