Puf!.. ideas varias pero todo dependerá del número de registros de tu bd. Si son muchos... quizás no sea muy factible hacer lo que quieres pero si no van a ser muchos registros a modificar, pues claro que se puede hacer lo que te piden.
La idea básica sería mas o menos que si el usuario pone en un registro el orden 5 tendrías que actualizar los registros con orden mayor o igual a 5. Para recorrerlos la consulta es tan sencilla como:
select * from <tu_tabla> where orden >= 5 ASC;
Una vez que tienes tu $row lo único que tienes que hacer es incrementar en uno el campo orden de todos los registros que te devuelve esa consulta, independientemente del valor que tenga y que sean consecutivos o no.
La consulta de modificación de un campo en un registro es:
update tu_tabla set orden=$row["orden"]+1 where id=$row["id"]
(revisa la sentencia, no estoy muy segura de que me falte algo, y ojo no te olvides de indicar la clave primaria en el where del update)
Eso es lo que se me ocurre apriori.
