OK, I can add a little to this:
ACS server service account has been given rights to log on locally, act as part of the OS, and to log in as a service. The machine seems to be correctly on the domain, and the domains show up in the database field within ACS when configuring authentication. The DNS servers were also changed on the ACS server to point to our new DNS (which is working fine for all other machines).
When I try to authenticate against ACS from a router, I see a message in the auth.log saying windows authentication failed with a code of 6L
So my question is, what has changed? What am I missing?