Sorry to hear about your trouble.
I don't play HOI MP myself, but if there haven't been any special problem on the HOI/host end during the period of trouble it seems reasonable to look on what has changed at your side.
It then seems likely that something has changed after all. From my experience with both those companies tech support, I would say they aren’t’ that bad. I would definitely make a try on the new providers’ customer support.
You don't need to be HOI specific when you talk with them, just provide the basics (such as Windows version etc) and then say you have an existing, installed, game that worked with the previous provider but not after connecting with them as a new provider (you haven't changed anything yourself, right?). They should take some extra care with a new customer that have left their archenemy Telia.
I wouldn't be surprised if the tech support asked why you haven't tried other on-line software. Surely you have some other relevant software/games. By seeing if other software/games work or not now is a very good way of narrowing down the problem.
If they can't be of any use at all, I would suggest you post again here with some more information. What did the tech support say to you, what software/hardware do you use etc (including HOI version). If you for some reason can't contact the providers support, just post more details here anyway.