Ok, I'm stumped. I've had this problem before, but I can't remember the exact steps I took to fix the problem.
I've created a cab with my web parts, I deploy it to our development server using stsadm win, it deploys, they show up in the catalog, but when I try to add them to the page I get the 'can't deserialize web part etc' error.
I've tried:
Deploying to the GAC
Not deploying to the GAC
Checked the permissions on the temp directory for the app pool account for portal server
Deployed it on my development machine fine.
Deployed it on a clean install of sharepoint fine.
Anyone remember what the trick is for this problem?