uncleroot,
я имел в виду чота вроде (повторюсь, я не настоящий сварщик):
$eng=array('a','o',...);
$rus=array('а','о',...);
$n_e=str_replace($eng,$rus,$nickOfNewUser);
$n_r=str_replace($rus,$eng,$nickOfNewUser);
$sql="SELECT FROM users WHERE nick=$n_e or $n_r";
$a=$db->query($sql);
if ($a->num_rows > 0) {
echo("не-не-не");
}
else {
continueWithRegistration();
}

Это, конечно костыль, но по идее должен сработать, не?