Sherlock:
I would go with Avaya. I'm not saying Cisco isn't good but currently I know that Cisco Call Manager / Unity has bugs in it which Cisco is aware of but no ETA on a fix as yet & this issue has been found since Cisco Call Manager 4. Cisco is easy to setup, deploy & maybe cheaper than Avaya but from what i'm hearing about Avaya it is currently better than Cisco with a little bit more complex in setup & deploying. I myself have only used Cisco Call Manager & Asterisk ( currently just Asterisk but on a small scale ). If i'm not mistaken Fujitsu & another company in Jamaica provide support for Avaya. There is also the possibility of using Asterisk and interconnection your locations where Avoxi now Dow Network provides service & support.
Let me know what your thinking & decision as i know persons at both Fujitsu & Avoxi / Dow Network among other places.