I spoke too soon. I *almost* have it working.
After a reboot, I can't connect to cups from machines on my lan. First, I need to go to http://localhost:631/admin.
Then I need to click Edit Configuration File. I then click save changes. It asks me for my root password and login and then restarts the cups server. I don't actually change the file.
However, after that everything works. Somehow, cups is not getting started correctly. I know it has started on boot because I can go to http://localhost:631
which is fine.
So, does anyone have any ideas on this rather weird error? It's annoying to have to remember to restart cups in this way after a reboot? I have made a temporary fix by putting the command services cups restart in /etc/rc.local. However, I feel that's more of a patch than a solution.