Problems with changing baud rate - device connected to Arduino Uno

Hi Robin,

Thanks for the answer,
I took into account that 115,200 bps might be too high, so I went for the 9600 bps.
Please look at the code - there is a message of switching the baud rate to 9600 bps.

I do change the baud rate of the GPS device connected to Arduino from 4800 bps to 9600. I make sure that the device changed the transmitting data rate to 9600, by monitoring the Tx line (the line by which the GPS device transmits to Arduino). I get good valid data from this line.
So the communication between the GPS device to Arduino is fine.
My problem is that data coming from Arduino serial port to PC is gibberish. It is not 4800 bps as it was in the beginning, and not 9600 bps, and actually I scanned the whole range of baud rates - and didn't get valid data at any baud rate.

The communication properties of the GPS device are standard - 8 bits, no parity, one stop bit.

Thanks.