Removing the pkg and obj folder and solution folder from the bin directory and rebuilding worked for many, It didn't work for me.
In my case it was because under the images to be deployed with the webpart, there was one image missing from the folder and visual studio was showing yellow icon besides it (because it was deleted outside the visual studio IDE). Due to this, VSeWSS 1.3 was not able to create the package for deployment.
I removed that missing image and deployment worked fine thereafter!
So ensure that you do not have any missing images linked in the Visual Studio IDE and then only deploy the solution.