As good a reason for not using a travel agent as I've heard in a long time. What kind of ticket ie: fare class were you booked. Were you revenue J in J P or Z.
Should not have been difficulty to book you on AC to YUL and then to FRA from there an option. If YYZ was canceled. There are a number of flights from YYZ to FRA so if one was canceled on a revenue ticket there should have been no problem. Whose sock was the ticket issues on, try to deal with them directly. The first airline has the money and that sounds like it would be AC. A warning however unless you have status they can also be mighty unhelpful. The agents in EWR were not able to help? I would be looking for another TA regardless.