Hopefully all you should need to do is add "SiteTree::enable_nested_urls();" to your _config.php file, and visit yoursite.com/dev/tasks/MigrateSiteTreeLinkingTask. If you have custom code relying on unique URLSegment values or using $URLSegment to generate links some things might break.

I upgraded using this:

mysqldump --opt --user=$user -p$password $oldDatabase -r db.sql
mysql --user=$user -p $newDatabase < db.sql

but get bad characters: å and Å
The site is in Norwegian so the bad characters are : øæåØÆÅ

Mysql command:
show variables like 'char%';
+--------------------------+----------------------------+
| Variable_name | Value |
+--------------------------+----------------------------+
| character_set_client | latin1 |
| character_set_connection | latin1 |
| character_set_database | latin1 |
| character_set_filesystem | binary |
| character_set_results | latin1 |
| character_set_server | latin1 |
| character_set_system | utf8 |
| character_sets_dir | /usr/share/mysql/charsets/ |
+--------------------------+----------------------------+

So I can't upgrade the site and it's driving me nuts trying to figure this out.