This one I'm most familiar with because I've done it or have been rebooked on them, but United is operating as codeshare for Air Canada who is the carrier. Your issue here is with Air Canada mostly since they are the carrier and can lock in the seats. But eventhough you guys booked the seats in advanced, the seats are never a guarantee on any airline, though you may say "I've done it in the past and this has never happened before", trust me it can and does happen quite often. The best that you can do is lock in seats as close as you can 24 hours in advance and then try your best to get better seats at the gate when the flight is closed. That is usually when the held seats are released (no shows, last minute cancellations, misconnects, etc)
The ticket counter can't help you because they are limited to just checking you in, the gate has a better chance of getting you the seats but only if someone is willing to switch. I've gotten that call to the gate for "an important message" only to be told someone wants my seat so they can sit with someone else. If it's a parent separated from their kid, sure I would do it all th etime. But if its an adult who is separated from another adult, who is not disabled, then no dice. It's the seat i locked in 24 hours ahead, and it's where my butt will stay planted.
p
Next time if you cannot lock it in online, just wait until you get to the gate and try your best to get two seats together that way.