That is not a legal private IP address range according to RFC1918 so they should not really be using it.
169.254/16 addresses are reserved for link local addressing (RFC 3927) - this is what a machine would assign itself should it be configured for DHCP and not receive an offer.
Given that their 169.254 segment is operational and working okay, I would go through standard troubleshooting techniques through the OSI layers:
1. check physical connectivity
2. check arp/mac address table entires are correct on switches and end hosts
3. check ip addressing of end hosts are on the same layer 3 vlan with no filtering/access control, with correct default gateways
4. check for any host-based access control - software firewalls etc.
If you could send printouts of arp tables, mac tables, routing tables and ip addressing configuration of some example hosts that would be useful.
Hope this helps, Ash.