From the client, try doing an nslookup or dig and make sure they are able to connect to the DNS server on the Mitel box. Make sure the DNS server on the Mitel box is running, and that it is forwarding requests on.
The Mitel box could be blocking DNS requests from the LAN as well, it shouldn't, but a bad ipchain rule could be in there.
Also, check what DNS servers the Mitel box is pulling from your ISP. You can add them into the DHCP scope, or manually assign them on the clients. Since they Mitel box is able to resolve names that should work.
As for Netbios names, you could manually put entries into DNS so all machines can resolve each other using DNS. If you just have one subnet, then you should be able to resolve by broadcast, but it will take a few minutes after a machine comes up for the name to be findable.
If you do a lot of local name resolution you may want to set up a WINS server with samba or a NT/2k box. If you are running 2k/XP clients and you setup a 2k DNS server you also can have all the clients register their own DNS automatically.