One more bit of info I've found along the way.
Trying to see what the difference between the California sample and our sample was, I downloaded the .mxd of the California map. Every layer had a ! by it, indicating the data wasn't there. I looked around, and found a "networkanalyst" folder, downloaded that, and pointed the map to that, and I had a full looking map.
Saving that .mxd and uploading/publishing as a service caused the same "database not found/layer is invalid" error, so obviously I need more than the .mxd. I tried uploading the "networkanalyst" folder as well, yet still ran into the same errors.
Saving the .mxd into that same networkanalyst folder (and pointing the layers to same folder) and uploading that, and publishing it as a service however, seemed to cause things to work out ok.
I'm thinking something's the matter with working with ArcMap on Windows, and uploading the data to a Linux server.
However, trying this exact step with our data gives the same old "database not found/layer is invalid" problem as before. I'm going to try to make a new map tonight to see if it's our data or something else.