It seems I always am answering my own questions here, but I figured out the problem for those who need to know.
I registered a datastore with the hosting server. When I looked at the server logs it was saying it failed to connect to the underlying database file (SDE). So I knew I had a database connection issue. I went to the database connection in the server manager, selected the appropriate datastore and hit "Validate." After doing so the layers published without issues.
The only mystery is why the first one published, then the others failed.