It's never been a problem for me. But I am the perfect Apple customer here, who has been using Macs as their main computer well before anyone at Apple even spoke the name "iPhone", so my experiences are very different then anyone in Windows land. I have no idea what needs to be done there, but it may just be a matter of migrating the right key folders.

When I get a new machine, I do one of two things. I either use the migration assistant that pops up during setup to suck all my data across, or I pull what I need by hand later. For migrating stuff for the phone by hand, all it takes is dragging and dropping three folders. One being the iTunes folder in ~/Music (for all music, videos, and apps), ~/Pictures/iPhoto Library (for all my photos) and the last one is ~/Library/Application Support/MobileSync (iPhone backups, IE SMS history, application data, etc). I did this just two weeks ago, moving these folders to my laptop for a weekend trip, then back to the desktop Mac when I got home. Address book, calendars, and bookmarks all sync over the air via MobileMe.

So far, my iPhone data has now seamlessly moved between 3 phones, and many software updates, including many restores done to run new beta versions. I've got SMS history going back to the first messages I received after buying the iPhone in 2007. Probably should clean some of it up soon, but it's never been a big deal.