Это будет работать, но это ОЧЕНЬ, ОЧЕНЬ ПЛОХО :
$check = mysql_query("
SELECT *
FROM Clients
WHERE Username = '$new_username'
AND Username != '{$_SESSION['Username']}'
") or die(mysql_error());
Это тоже сработает и рекомендуемый способ сделать это:
$check = mysql_query("
SELECT *
FROM Clients
WHERE Username = '" . mysql_real_escape_string($new_username) . "'
AND Username <> '" . mysql_real_escape_string($_SESSION['Username']) . "'
") or die(mysql_error());