I feel your pain.

1. VS auto increments the version number by default. verify that
the version number you entered in your dwp file is the same as the
dll.
2. are you using a resource that WSS_Minimal doesn't give rights to
by default. Opening files on server or calling web  service? You'll
need to edit the WSS_Minimal.config file.
3. Are there multiple entries in the web.config file for your
webpart. This happened to me as a result of VS auto incrementing
the version number.
4. Have you entered the publickeytoken attribute into you dwp file
for your webpart?

resources i found helpful:
www.msdn.microsoft.com/.../...eployingwebparts.asp" target="_blank" rel="nofollow">www.msdn.microsoft.com/.../...eployingwebparts.asp

www.msdn.microsoft.com/.../...eployingwebparts.asp" target="_blank" rel="nofollow">www.msdn.microsoft.com/.../...eployingwebparts.asp