Stsadm upgradesolution vs. deploysolution

upgradesolution != deploysolution

There are certain times when you can use upgradesolution, primarily only when you haven't added or removed any files from the project. 

The list of the constraints for when you cannot use stsadm –o upgradesolution:

• The following operations are not supported in solution upgrade.
• Removing old Features in a new version of a solution.
• Adding new Features in a solution upgrade.
• Updating or changing the receiver assembly for existing Features in a new version of a solution.
• Adding or changing Feature elements (Element.xml files) in a new version of a solution.
• Adding or changing Feature properties in a new version of a solution.
• Changing the ID or scope of old Features in a new version of a solution.
• Removing Feature elements (Element.xml files) in a new version of a solution.
• Removing Feature properties in a new version of a solution. 

So if any of the above cases apply to you, you should do a retract/delete/add/deploy solution.