Hello everybody, I stumbled upon this topic while struggling through the same problem as everyone else. I found the solution here: http://www.rjanick.com/2012/11/26/seeed-studio-bluetooth-shield/
The sketch lists the Tx and Rx pins as 6 and 7. In the link above he uses pins 2 and 3.
What worked for me was to do the following (from the link above):
Shield: connect jumper from Rx to pin 3; Tx to pin 2
Code: #define RxD 2
#define TxD 3
After uploading this change (and resetting the arduino) the BT Shield began flashing green/red!! Discovered by my SII!! Success!!!
EDIT: I realize that this post was started quite a while ago, but as this seems to be a common problem and the last reply was recent, I thought I would share a solution that works XD