Check in the Configuration ... Shipping/Packaging ... and make sure that this is marked 0 for No:
Order Free Shipping 0 Weight Status
If there is no weight to the order, does the order have Free Shipping?
0= no
1= yes