Te sucede por què haces:
if ($accion == "nuevo"){
$sql = "SELECT * FROM users WHERE usr='$usuario'";
if(mysql_query($sql)){
print "Lo sentimos, el nombre de usuario que ud. intenta registrar ya existe.";
exit;
ahí dices... "si se ejecuta la consulta correctamente .. muestra el mensaje" .. Y de eso no se trata sino de que veas el resultado de esa consulta . no de que si se ejecutó bien o no ...
Debes usar la función:
mysql_num_rows() o bien SQL con su COUNT() ...
Con esa funciòn cuentas el numero de registros que te arrojó tu consulta .. ya sabes que si el resultado es 1 .. ese usuario existe .. y si es cero . .no existe (a su vez no debería existir ninguno repetido .. )
www.php.net/mysql_num_rows
Un saludo,