Hola,
para generar URLs que tienen tildes, eñes y espacios sugiero hacer esto:
//le cambio los espacios ,los tildes y las ñ.
$url_nueva = str_replace(array(" ","á","é","í","ó","ú","Á","É","Í","Ó","Ú","ñ","Ñ"),
array("%20","%E1","%E9","%ED","%F3","%FA","%C1","%C9","%CD","%D3","%DA","%F1","%D1"),
$url_vieja_con_tildes);
espero que sirva.
byp.