Same problem on my iPhone 3GS. Updated to 5.0 and then 5.0.1 and cookies always swtich back to "never". I don't sync with WiFi. Although, I do still MobileMe wirelessly and sync via iTunes for music, podcasts, txt and phone logs.
Someone suggested clear cache and cookies in iPhone Safari, but I haven't tried it.
I had the same issue. Every time I synced with iTunes my Safari browser settings would be changed to "never accept cookies". This affects the Safari browser and any app that uses built-in browser to work. An example would be the Best Buy Reward Zone app. I have an iPad and iPhone; both through work where we utilize Exchange email. The iPad never has the issue despite having the Fraud Setting turned to On. Both my devices are Verizon based. iCloud doesn't seem to have any bearing on it either.
Go to Settings > Safari > Fraud Warning > Set to "Off"
Of course, you will also need to make sure you set Accept Cookies back to at least "From Visited". This can be found at Settings > Safari > Accept Cookies > Set to "From Visited"
Try a sync in iTunes now and see if it sticks.
There is a correlation between this and the Safari Safe Browsing function that occurs during an iTunes sync. You can see this step during a sync at the very top of iTunes. Hope this helps.