Vale, lo encontré, a medias, ya que no funciona en FireFox. Se le añade este a los parametros del Flash, y ya queda por debajo de todos los elementos.
<param name="wmode" value="opaque" />
Si alguien sabe la forma de conseguirlo en FireFox... Me haría un favorazo!
Esto lo encontré en las FAQs de Flash, junto con otra solucion que es meter el flash en otra capa y jugar con los z-index de las dos capas, pero nada, el Flash sigue quedando por encima (con esta solucion no funciona ni en explorer..)
Saludos!