¿Qué tarda Google en el modificar los enlaces?

[aloqui]

Google normalmente utiliza el texto dentro de la etiqueta <title>
El tiempo que tarde en actualizarse depende de cuantos enlaces encuentre hacia dichas páginas y de lo importante que considere a tu web. Supongo que en un par de semanas las secciones importantes deberían aparecer con los nuevos títulos.

En cuanto al PageRank, podrías subir a PR5 si las páginas con PR7 son de un tema similar y no tienen demasiados enlaces, y además el tuyo no tiene el atributo rel="nofollow".
Pero yo no contaría con ello, lo mas probale es que subas a PR4.

En cuanto al cambio de muchas de tus URLs, te recomiendo que si no te complica mucho, modifiques el fichero .htaccess para incluir redirecciones 301 desde las URLs antiguas hacia las URLs nuevas. Así no perderás los enlaces previos que tuvieras en otras webs con las URLs antiguas, y además los buscadores contarán dichos enlaces con las nuevas URLs.