Lilypad + bluetooth + C# communication problem

Sounds to me like a wrong baud rate or parity error. Can you check that all your baud settings are similar for the bluetooth and arduino?