Are you using paypal standard? It may be that the shipping cost is being passed in by the form and overriding the shipping you have set up. You might be able to just delete the hidden form element that passes in the zero dollar shipping and then it should use the paypal shipping rules.