These responses are amazing. Thank you so much for your helpful replies! At this point I think I might recommend they drop a second Cat5e line.

In everyone's experience, how much extra does it normally cost to install Cat6 vs. Cat5e? Does Cat6 take literally twice as long to install as Cat5e? And does Cat6a take a lot longer than Cat6?

I think the phones are Mitel, but I'm not sure. I'd be interested in reading people's thoughts on which manufacturers are generally considered to be the most seasoned in the technology.

My co-worker and I weren't in the loop on the decision to go with a VoIP system and were caught off-guard by the announcement. I'm not even sure the brand has even been decided yet--just the vendor. When I researched Mitel for a customer several years ago, they were already seasoned in the VoIP market and looked like they were in good shape. My wife works the phones in customer service for a small company with an Asterisk-based VoIP system. Because it's VoIP, she can work from home over a VPN using a headset attached to our computer to take calls (as a matter of fact, she has yet to work a day physically located at the call center). It has been a robust system, for all that I can see.