ok - first of all - DON'T just press the shortcut to your address book!
Choose: Menu>Address Book>Options>Advanced>Copy All to SIM
Once they have all copied across, take the SIM and put it into your 5800. Switch it off and wait for about 30 seconds. When you go to the address book it should tell you that there is a new SIM inserted and ask you if you want to import all the numbers. When they have all copied across switch back the SIM cards.
Let me know if you need any more help
