That might be related to an extension that hooks into the collectTotals() methods, which are called on every refresh of the cart.
If an extension relies on data that is not present yet at the first time the totals are collected, it might mess them up.
To debug, search for _collect_totals_ and _collect_totals_ in all config.xml files below app/code and see in which modules you get results (excluding those from core/Mage). You'll find observer definitions for events like sales_quote_address_collect_totals_before.
Disable all extensions you find, and if this solves the problem, enable them again one by one until it appears again. Then it's time to examine the observer code and/or contact the extension vendor.
Best Answer
If you want to edit
app\design\frontend\THEME\PACKAGE\template\checkout\cart\totals.phtml
, you can use