Wrong characters received with Bluetooth Mate Gold using Software Serial

Question

I have a Bluetooth device from Sparkfun which I would like to use with the Arduino Mega. If I connect the module via the hardware serial pin everything works fine but when I use other pins like 12 and 13 with SoftwareSerial, the communication doesn't work as expected.

THE CODE

#include <SoftwareSerial.h>

int bluetoothTx = 12;
int bluetoothRx = 13;

SoftwareSerial bluetooth(bluetoothTx, bluetoothRx);

void setup()
{
  //Setup usb serial connection to computer
  Serial.begin(9600);

  //Setup Bluetooth serial connection to android
  bluetooth.begin(115200);
  bluetooth.print("$$$");
  delay(100);
  bluetooth.println("U,9600,N");
  bluetooth.begin(9600);
}

void loop()
{
  //Read from bluetooth and write to usb serial
  if(bluetooth.available())
  {
    char toSend = (char)bluetooth.read(); 
    Serial.print(" Receiving: ");
    Serial.println(toSend);
  }

  //Read from usb serial to bluetooth
  if(Serial.available())
  {
    char modeS = Serial.read(); 
    Serial.print(" Writing Blu: ");
    Serial.println(modeS);
    bluetooth.print(modeS);
  }
}

I'm using an Android App (BlueTerm) to test the communication.

Here is what I get when sending a letter from Android to Arduino.

 Receiving: ÿ
 Receiving: ÿ
 Receiving: ÿ
 Receiving: ÿ
 Writing Blu: d
 Writing Blu: d
 Writing Blu: d

I'm not able to receive anything from the Arduino.

I've tried decreasing the baudrate but nothing changed. Do you have any advice?

Update

I have tried without the following lines but nothing changed... It seems that the module can be used only with the hardware serial pins 0 and 1... It's a shame

bluetooth.print("$$$");
delay(100);
bluetooth.println("U,9600,N");
bluetooth.begin(9600);