Hi all. I just wanted to report my fix. It turns out the issue was with my router. I have a D-link DIR-655 router. I found a fix on the web where someone turned off multicasting on his router. To do this,
1. Log in to your router
2. Click Advanced -> Advanced Network
3. In the "Multicast Streams" section, make sure "Enable Multicast Streams" is unchecked.
4. Save changes, wait for router to reboot, and enjoy AirPrint. :D
I hope this helps someone. I've been tearing my hair out for the past few days. O_o
Nice to hear a happy ending. :D