That's actually good news - it narrows down the problem considerably. Either the weights aren't set for the products or the weight calculation in uc_usps got screwed up. I suspect the latter, since you said you checked your product weights and because a lot of work has been done on the _uc_usps_package_product() function recently. Maybe Lyle can quickly spot the problem.

A quick way I use to see if the order weights are set right is to set up the Weight Quote shipping method to charge $1/lb. for shipping - that way on the checkout page when you get shipping quotes the shipping charge for Weight Quote will be = the shipping weight of your order. (Change this to $1/ounce if you want a more precise weight measure.) If Weight Quote gives the right answer then the problem is definitely in the uc_usps module.