I faced the same problem. Did everything everybody else previously mentioned.

How I solved it. I created a web part project under VS2005 with WSS extensions installed. Then built the project (and this is the important bit) and deployed it using VS2005's Build>Deploy <Project> menu. VS2005 did its magic and got it working.

BTW, deleting the Temporary.snk file did not work for me.