The tutorial isn't worth watching. I assume your module looks like those in the second link - a plain-vanilla HC-05. The first bit of code should be redundant, the second looks like it is trying to do something else, which might be a problem.
The code below is a bare minimum to prove up the bluetooth - nothing fancy. It will work with a USB connection to the PC without any change. The code you quote may be appropriate for the Pro Mini but this is all you need for the Uno.
Use BlueTerm on the Android. Once you know the code is kosher on the Arduino, all the work is done at the Andoid end. This works on my Android phone and my XP laptop via bluetooth as well as the XP desktop via cable. My ICS tablet can see the Uno, and pair with it, but will not talk to it. This is clearly down to the tablet, and you may have a similar problem. Both phone and tablet use BlueTerm.
void setup()
{
Serial.begin(9600);
Serial.println("OK then, you first, say something.....");
Serial.println("Go on, type something in the space above and hit Send, or just hit the Enter key");
}
void loop()
{
while(Serial.available()==0)
{}
delay(500);
Serial.println("I heard you say: ");
while(Serial.available()>0)
{
Serial.write(Serial.read());// note it is Serial.WRITE
}
Serial.println("");
}