I have the exact same problem.
I have called Apple support and have also logged a bug (ID #7226841) in the Apple Developer bug tracking system.
Here is the text from my bug report:
15-Sep-2009 09:25 PM <snip>:
Summary:
iPhone v3.1
iTunes 9.0 for Windows XP
When synchronizing my iPhone 3G 16GB with iTunes, iTunes synchronizes all relevant components (bookmarks, calendar, notes, music, ringtones, podcasts, etc.) and then erroneously reports that there is not enough free space to sync photos and albums when, in fact, there is.
At the present time I have over 300MB of free space on my iPhone (confirmed in both iTunes and in my iPhone settings). I have selected 43MB of photos to synchronize between iTunes and iPhone, yet I continue to receive the error message (see attached file).
Steps to Reproduce:
1. Attach iPhone to PC via USB.
2. Configure iTunes to synchronize only selected music, applications, ringtones, podcasts, photos, etc. - specifying only selections that fit within the available storage space on the iPhone.
3. Select "Sync only checked songs and video" from the Summary tab.
4. Initiate synchronization by clicking "Sync"
Expected Results:
The synchronization should initiate and complete without error just as it did with iPhone v3.0 and iTunes v8.x.
Actual Results:
iTunes reports that "No photos were copied to the iPhone "<name of iPhone>" because there is not enough free space on the iPhone to hold your photos and albums.
Regression:
This problem did not occur with iPhone 3.0 and iTunes 8.x
Notes:
I followed all three of the troubleshooting steps in the Apple KB article to no avail:
http://support.apple.com/kb/TS1503
If I synchronize one item at a time, sequentially adding additional data (first music; second, music and ringtones; third, music, ringtones and podcasts, etc...) and perform multiple syncs to get all data onto my iPhone, all selected components synchronize without error - leaving about 250MB of free space remaining. If I then follow that up with a subsequent full automatic sync of all selected components, the error message RE: not enough free space returns, my photos are deleted and the synchronization stops.
This error only occurs when the synchronization attempts to reconcile and synchronize all selected components automatically.
'iTunes_error.bmp' was successfully uploaded