I eventually solved this. 404 is apparently what you get with a RIA service when there is some underlying error before you get to your execution code. The best way to get at that for me at least, was to create the svc file that doesn't exist (pretend like it's a normal wcf service), place it in the ClientBin folder, and then use Fiddler. Once the file was there, my 404 became a 500, with a description of the error in Fiddler.
In my case, the error was the SqlServerTypes libs were not installed on the server, and it was throwing up.
Hope it helps someone.