I've found the reason for this problem and it's absolutely very strange in my honest opinion.
Short Answer:
The Problem was caused by the Currency being set in the Reports (in Show Currencies using) SUPERSEDING the Personal Currency of the User.
Long Answer:
The User wishes to see the Summarized Headers of the Reports in his own Personal Currency.
For example:
Records 1, 2, 3 are all in USD (CurrencyIsoCode = USD). However, User wishes to see the total of these records as converted to EUR (this is his Personal Currency) in the Summarized Header of the Report.
We expected this to be the case since we've actually seen another Report whose Summarized Header changes depending on the User's current Personal Currency.
But apparently this is not the case. Whatever is being set in the Report's currency setting (Show --> Currencies Using --> EUR) will SUPERSEDE the Personal Currency of the User.
The reason why we could easily change the currency of the Summarized Header in the other Report was that, we never touched it after we activated Multicurrency.
If you will retrieve the xml for this Report in Eclipse, you will see that it does not have a tag called:
<Currency>EUR</Currency>
While the Report that has that tag lost it's dynamism in having the currencies in its Summarized Headers as that of the User's Personal Currency.
So our Solution then is to retrieve our Reports to Eclipse and ensure to erase the tag EUR so Personal Currency can be used.
Sort of Off Topic:
It is really strange for Salesforce not to add the option in the Reports that would allow us to choose to use the Personal Currency of the User in order to achieve a sort of dynamism in the Reports rather than making it all Static.
When you are doing things like this (manual conversion of currency fields), the target of the conversion (Amount_Converted__c) needs to be of type Number, not type Currency.
When it is a currency type, SFDC OOTB rules for how currencies are displayed are governed by the record's currency and the user's currency.
When I've done what you are doing in the past, I've named my custom field Amount_EUR__c to be explicit about what the field's content contains.
Of course, another option you might consider is to make your org's currency = EUR - this way, all reports and dashboards will roll up currencies to EUR automatically.
Best Answer
Actually, I'm pretty sure this is intentional. The system makes no assumption about what the user meant to input. Automatic conversion might result in incorrect values. The user should be responsible for updating the value, if it's appropriate.
Uses that are primarily single currency are just trying to fix a unit error, and users with multiple currencies would probably choose to update the value accordingly without system assistance. It's unreasonable to assume a default position that users made two simultaneous input errors. If the current changed the payment, for example, the user would have entered the new value.