Hi.. I had the very same issue (iPhone working perfectly, update to 3.1 caused it to crash and stick in recovery mode 'connect to iTunes' etc.) First you should try all the steps in this support article:
http://support.apple.com/kb/TS1275 - If you phone the AppleCare support line, this is all that vthey'll talk you through. If that doesn't work - and it didn't for me, but has for some people (especially the 'new user' attempt), then you should make an appointment to see a tech specialist at your local Apple Store Genius Lab.
I had my appointment at the Genius Lab today. Here's the lowdown straight from the Apple Genius' mouth— apparently there IS a known issue and it resides not actually in 3.1 but in the process of removing 3.01 before 3.1 can be installed.
In the words of the Genius "3.1 is actually really good, it's 3.01 which was actually a real mess".
Hope this helps.
