As of Dec 2012, Amazon currently supports migrating an AMI to a different region through the UI tool (Amazon Management Console).
So, how I've done it is.
1. From the AMI determine the Snapshot-ID and the way it's connected (e.g. /dev/sda1)
2. Select the snapshot, click "Copy", set Destination region and create the copy
3. Select the new Snapshot, click "Create Image"
- Architecture: (choose 32 or 64 bit)
- Name/Description: (provide one)
- Kernel ID: while migrating a UNIX system AMI, if you select "default" it's going to fail. What worked for me was to go to the Amazon Kernels listing here to find the kernels Amazon supports, then specify it when creating the image)
- Root Device Name: /dev/sda1
- Click "Yes, Create"
4. Launch an instance from the new AMI and check that you can connect.