Have you checked if the currency conversion values are set correctly?
You can manually update the currency rates :
1. On the Admin menu, select System > Manage Currency Rates. 2. Click the rate you want to change, and type the new value. 3. When complete, click the Save Currency Rates button.
This should ideally resolve the problem.
In addition, if you are looking to show shipping costs based on dynamic currency changes, you can try the StorePep Integrated Shipping & Tracking extension for this purpose.