PayPal changed (and hence broke) the way shipping used to work. There is no "override profile based shipping" checkbox any more. They migrated all your settings to rules and those rules are not being overridden by transactions based shipping!
Please make sure you remove any shipping rules that PayPal automatically added to your PayPal Profile under Shipping Calculations.
Related Reading:
http://www.pdncommunity.com/pdn/board/message?board.id=basicpayments&message.id=14609#M14609
