Hi - I'm another Arduino Newbie.
For what its worth, I've had exactly the same problem as described by the original poster.
I was using Win XP SP 3, Arduino 1.0 IDE, Arduino Uno board.
Same problem - string of rubbish text whenever I changed the baud rate from default of 9600.
I ran the same code again, this time on a different laptop using Ubuntu 13, Arduino1:1.0.5 and the same Arduino Uno board.
The word "Test" appeared at all baud rates.
So I conclude that this is not a problem with the Uno or the Arduino IDE; it is a problem with Windows XP; although I don't understand what.
I suggest installing Ubuntu (It is really easy to set up as a dual boot if Windows is already installed), and running the Arduino IDE from Ubuntu rather than WIndows.
Hope this helps in some small way
Best wishes
Dave