This has to be a simple solution.For discover the sheild in your mobile phone red light on sheild must be blinking.First of all try this solution- Push reset switch loacted on arduino board.after pushing reset switch MCU will send the commands to set it to discover mode.
also make sure that you have chenged the baud rate of sheild at hardware level.otherwise u cannot see correct message which you had sent it from pc.if 9600bps does't work then try out with default sheild baud rate which is 38400bps.
Also check jumper connection on sheild .