Have we ruled out a problem on the sending side?
Opening the serial port from the PC side resets the arduino. The Arduino isn't running your program for a couple seconds after reset. So, if you open the port and write to it right away / without a delay, some of the sent output gets dropped on the floor (by the bootloader).
If you don't delay after opening the port, it might be worth a try. And could you post your whole sending-side code?
-br