I fixed it, though it wasn't a problem with anything except my setup. If anyone is experiencing a similar issue, our IIS server somehow had regained Anonymous Access privileges for the rest services virtual directory, despite the services being secured at the ArcGIS Server Manager level. This isn't the first time I've dealt with "creeping permissions" on this server, I guess they like to keep me on my toes.
As far as why it works in 3.5 with that configuration but not 4.0, I'll leave that to the smart people 🙂