I would think that there is something wrong with the serial port settings. But you say you have checked it. Did you try the other example? It uses the software serial port. I don't know if it still works in arduino-0009. I'll have a look around on my system for a version which uses the software serial port.