Welcome back.
Access to the new expansion areas such as the city of Ishgard indeed requires full story completion through all the patch scenarios that were added which extend the storyline past the destruction of the Ultima Weapon to the 2.55 patch - there are five separate patch main scenarios actually (the last one was done over two parts but is classed as one patch): 2.1 A Realm Awoken, 2.2 Through the Maelstrom, 2.3 Defenders of Eorzea, 2.4 Dreams of Ice, and finally, 2.5 Before the Fall.
All these patch scenario quests lead into one another successively, functioning as one long storyline. The reason access to Ishgard requires the patch main scenario to be completed is because lore wise the city is closed off to outsiders and the circumstances that allow the player to visit it are extraordinary (explained at the end of the 2.55 quests) - even after the player gains access to it, lore wise it's still a 'closed' city (to enter after gaining access you either have to teleport in or speak to a guard at the Gates of Judgement to enter the city, rather than just waltzing through the front door freely).
As for the old HM Primals, they haven't been considered 'end game' for a couple of years now - however, due to the Duty Roulette you should still be able to get a party for them, just don't expect to get a party queued immediately, as it will often take time. Another thing to remember is the DF only looks for players matched to your current language setting - if it's only set for English it will only be looking for players who also have English set as their language, making the pool of available players wanting that trial or dungeon that much smaller. Of course the other side of that coin is communication barriers, but that's life I guess, you gain some, you lose some. You could also try creating a party through Party Finder and shouting out for help as well, but just be aware people in PF usually expect you to know the duty inside out unless you specify it's your first time there.
Either way, don't be discouraged! The huge twist at the end of 2.55 (as well as the many twists and turns in Heavensward's storyline) definitely are worth all the effort trudging through the often monotonous patch storylines.