Go back to the source- your landlord and the tenancy agreement. How was the deposit held?
Next, find out whether the old and new agencies belong to any professional bodies like National Association of Estate Agents (NAEA), Association of Residential Letting Agents (ARLA) , Association of Residential Managing Agents (ARMA), National Approved Letting Scheme (NALS), UK Association of Letting Agents (UKALA), Ombudsman for Estate Agents (OEA)
Check this article for links:
Agents, Letting Agents and Property Managing Agents - LandlordZONE
Write to the professional bodies of your ex-agents and the new one. Ask them to help you negotiate this maze- these bodies have no powers to make decisions but they could help in establishing who you should chase for your deposit.
And of course, the old chestnut of bad publicity- in a very competitive market, the estate agents are very anxious about bad publicity. Run your imagination wild- Watchdog, local papers, lettings forums, etc.