May 7th was a Monday. The CO website lists an 9:35am flight out of BNA since the OP mentioned he started his trip in Nashville. CO2999 arrives at EWR at 12:59pm with an onward connection of CO84 at 4:05pm. Since the OP didn't include the part where he cleared security, his story must involve the actual gate, not the check-in counters.

The OP used a TA and it should have been their job to guide the OP better. After all that's what we've recommended here frequently to infrequent flyers. The TA should have informed the OP that the gate counter would not open until an hour before departure and instructed him on the ways of getting his seats changed.

Of course a good Continental GA could have avoided all of this by simply stating they were closed until an hour before departure and directed the OP to the nearest airside customer service center (unlikely, yeah but still..).

Perhaps one lesson learned from this could be for Continental to modify their flight confirmation e-mails with a "Helpful hints for travellers" which could include some of these pointers. It would not have helped the OP since he used a TA but perhaps it would avoid at least some of these posts and it's certainly not all that expensive to put up another link on the webpage.