Stimmt denn überhaupt die Baud-Rate?
Mein Bluetooth modul (ohne den shield) werkelt nur bei 9600. Ich glaube mal was gelesen zu haben, das man das teilweise vorher testen muss/einstellen muss.
Dein Ansatz mit Softserial ist schon gut. Wenn du USB dran hast geht mein Bluetooth modul z.b. gar nicht auf pin0 und 1. Ich nehm immer 2&3 bzw welche ohne pwm 
Ich hab auch immer wieder Probleme Rx/tx auseinanderzuhalten. Ich steck das einfach immer um wenns net klappt. Kann sein das du den BLuetooth Shield dann einmal vom Strom nehmen musst weil sich das Modul aufhängt dabei.
Auch musste drauf achten ob es 3.3V oder 5V will 
und ob ggf. auch dein Pairing device funktioniert.
Es gibt im learning auf arduino.cc unter commuication nen Beispiel wo glaub das was auf Serial reinkommt auf Bluetooth serial ausgegeben wird und andersrum.
Das kannste auch mal testen um ggf. Fehler in eine Richtung auszuschließen
Praktisch auch immer wenn du Softserial nutzt dir alles parallel auf Serial auszugeben am Serialmonitor um einfach sicher zu sein das auch dein Restcode stimmt.
Also ich würde:
1.Baudraten durchtesten
2.Verkabelung checken und auch rx/tx tauschen wenn ich mir eig. ziemlich sicher bin.
3.mein Programm mal checken und immer alles auf Serial parallel ausgeben lassen.