So as it turns out, my banking troubles were not over afterall. I suppose I should be clear in that I am griping about the VISA division of my bank. The regular accounts I have just work like clockwork. It seems that when you call to activate a new card, the activation process is not straightforward. When an agent says everything is fine, what they really mean is that you will have to call in at least once more and your spouse is also going to have to call in to activate her card too, despite the agent assuring you that her card can be (and now is) authorized as well.
In the end I did cajole the bank into activating my card and ensured that the travel agent actually used the card to book the trip. Honestly, if I never book through the Flight Center again it will be too soon.