“No suitable Destination Host found by cups-browsed”

I was able to get my printer working. This seems to be some sort of bug in cups-browsed, which is a program that tries to automatically install every printer on the network. After removing cups-browsed I was able to manually add the printer, and was able to print without rebooting before hand.

First: uninstall cups-browsed

sudo apt-get purge --autoremove cups-browsed

Next: Restart your computer

Finally manually add your printer

1. In Ubuntu 18.04 go to settings -> devices -> printers.
2. Click on 'Additional Printer Settings'.
3. Click on Add
4. Under Network Printers select Find Network Printer. Enter the IP Address that your server running CUPS has. Once you follow the steps to install your printer you should be able to print consistently without rebooting.