Hola T4keOveR,
Puedes hacer sencillamente una consulta SQL:
Código PHP:
$user = $_POST['user'];
$sql = "SELECT '1' FROM `usuarios` WHERE `username`='$user' LIMIT 1";
$result = mysql_query( $sql ) or die( mysql_error() );
if( mysql_num_rows( $result ) > 0 ) {
echo "El usuario $user ya existe en la BD";
} else {
echo "Todo bien, no existe $user";
}
Saludos.