Oops - sounds like I may be in the same situation as you, fdl.
Could I ask a couple of questions?
Firstly, which country issued your EASA licence? Mine is Germany and there isn't much on the licence to show it was originally issued in the UK. The only place it appears is in section II where the country code of original issue is shown as GB.
Secondly, can you give any indication where you discovered this information.
Possibly if my German licence is more acceptable to them, that might be another option for you - SOLI again to another country. Certainly not a pain-free option, though.