Hola de nuevo,
Diria que al final hemos conseguido solucionar el problema. Tambien he aprovechado para reducir un poco el codigo, y la llama echo le he incorporado toda la parte constante de los enlaces.
Código PHP:
<?php
$enlace[1]="http://www.youtube.com/v/60KBUdgRCRw&hl=es_ES&fs=1&color1=0xe1600f&color2=0xfebd01&border=1";
$enlace[2]="http://www.youtube.com/v/gGDS_Q15xsg&hl=es_ES&fs=1&color1=0xe1600f&color2=0xfebd01&border=1";
$enlace[3]="http://www.youtube.com/v/ELvU4inKfQI&hl=es_ES&fs=1&color1=0xe1600f&color2=0xfebd01&border=1";
$enlace[4]="http://www.youtube.com/v/gjuX9pwcjJ0&hl=es_ES&fs=1&color1=0xe1600f&color2=0xfebd01&border=1";
//Contar enlaces
$total_enlaces = count($enlace);
//Genero numero aleatorio sin superar a enlaces
$aleatorio=rand(1,$total_enlaces);
//Escribo el vinculo
echo "<div align='center'><object width='340' height='285'><param name='movie' value='$enlace[$aleatorio]'></param><param name='allowFullScreen' value='true'></param><param name='allowscriptaccess' value='always'></param><embed src='$enlace[$aleatorio]' type='application/x-shockwave-flash' allowscriptaccess='always' allowfullscreen='true' width='340' height='285'></embed></object></div>";
?>
Lo pongo aquí para si le resulta útil a alguien.
Un saludo!