Magento has quite a big bug which enables the shipping module to calculate shipping costs without discount or shipping rules (if they are applied).
It cost me hours to find a workaround, so if you use it, I’d really appreciate it if you refer to this blog.
How I fixed it
Add the following code at around line 77 (in the collectRates function):
$s_price = $request->getPackageValueWithDiscount();
Now, the shipping rates are calculated on the subtotal minus the discount. I hope this solves the problem (it does in 1.7)