Bueno gente.
Al final la solución a mi problema ha venido rápido:
He hecho un callback final (al terminar de ejecutarse las dos animaciones).
Este callback, coge estos dos elementos con los que nos hemos movido, y los recoloca a nivel DOM uno delante del otro (insertBefore e insertAfter).
con esto he conseguido tener el DOM exactamente igual que lo visual y no me da fallos ni problemas :)
Aquí el ejemplo final (solo queda recolocar las flechitas (cuadros rojos y azules) para que al bajar el primero aparezcan las 2 flechas (y el que sube solo tenga flecha de bajar).
http://jsfiddle.net/L8qebbo5/4/
Gracias por la ayuda!!! :)
Javier