Ok, support takes a while, and I figured this out in the mean time. The underlying source of the problem is that when Sitecore is shipped, its default publishing target is called "Internet". I changed the value of /sitecore/system/publishing target/ "Target Database" field value to "web", because my users are accustomed to seeing it that way. My connection string has been updated accordingly.
<add name="web" connectionString="..." />
If you look in the Publishing Service site's /config/sitecore/publishing/ directory, there is a file called sc.publishing.xml. Inside of the <Targets> node is where targets can be edited or additional targets can be added. The default target that comes shipped with Sitecore Publishing Service is <Internet>. Now, here's where I'm not sure if I followed the proper methodology, as the Sitecore Publishing Service documentation states that you're not supposed to edit any of the files within the /config/sitecore/ folder. I'm sure there is a way to patch this in, but xml patching is not one of my favorite past times. If someone can recommend a better way to do this, feel free to interject. Here's what I changed:
I renamed the node to "web" to match my Target Database value. The site is now publishing perfectly.