Hola,
En los comentarios de los usuarios de array_multisort() (
www.php.net/array_multisort) comentan como pasar de un array multidimensional a un conjunto de arrays para cada columna. No seria dificil crear una funcion generica a la que pases el array multidimensional a ordenar y otro donde especifiques las columnas a ordenar y su orden y que devuelva otro array multidimensional como el de entrada pero ordenado.
Ahora no tengo tiempo, pero luego si saco un rato intento hacerla.
Saludos.