Restoring from the previous phone seems to work fine for most people. There have been a few scattered reports about restored apps not working properly (e.g. Navigon), but that can usually be resolved by reinstalling only these apps.
In the end, it's up to you. Personally I have started from scratch, and it wasn't really that much work. Most of it was re-configuring my various email/Exchange accounts, and switching over two different one-time password generators (Google Authenticator and another one I need for work), which are designed to be bound to a specific device (so this has to be done in any case even when restoring from a backup). Everything else (locally stored contacts, photos etc.) are easily restored either by syncing from a computer or from iCloud.