I've just had to do this for a school that we manage. I used the following script:
EDIT: One thing to note, this might need breaking into two parts,
then do Get-PSSession|Remove-PSSession and reconnect to the instance with the same credentials, otherwise the creation of the new GALs will fail due to incorrect permissions.
I've run it on a test site and it worked, and just running it on a live site now. Might be better to copy and paste a line at a time, in case of any errors (it ran fine once, but second time I got an error on the New-GlobalAddressList cmdlet - which is how I found this thread trying to work out why it failed..
