I personally find it easier to advertise printers like this using DNS-SD. Basically instead of having macs advertise AirPrint printers one per VLAN, you use your existing DNS to advertise printers to everyone.

All you really need is a print server (can be a mac with print sharing on or unix/linux or even windows with IPP printing enabled) and a BIND DNS server (again can be a mac or linux/unix or windows running BIND).

We use it to advertise our printers to 6 different buildings on two different campuses.

Helpful info can be found at http://www.dns-sd.org

If your interested let me know and I can walk you through setting it up

the linux tool avahi in reflector mode could also help.
have the linux box with avahi sitting on the vlans you need to broadcast bonjour traffic between and your away, no mess no fuss

There are some weird things going on here...

Each school has its own VLAN therefore we needed a Mac on each VLAN to broadcast a few printers via Airprint for iPad printing. It was working fine most of the year.

Now, however, we are seeing printers from different VLANS come-and-go. Additionally, in OS X, if you add a printer you now see tons of printers from other VLANS too. Unless Apple drastically changed the way Airprint/Bonjour worked something is very wrong!

Check with your transport folks. We've seen newer versions of Cisco IOS have the ability to automatically broadcast Bonjour requests to all subnets or they may have manually setup multicast DNS to route across subnets.

I'd recommend Printopia: http://www.ecamm.com/mac/printopia/
I've used it in a lot of different settings & never had a problem.

UPDATE:

It was our wireless solution. We had applied a update in February that added a whole host of Bonjour/mDNS/Airprint/Airplay management to our wireless controllers. However we didn't fully read the patch notes and missed it.
The default setting applied and the controllers are routing all Bonjour/mDNS/Airprint/Airplay traffic to every VLAN.

We have a wireless guy scheduled to come out in a few weeks to get us config'd correctly.

Ty for everyones help!

Yes,

more and more Vendors offer now
either dedicated Bonjour Gateways
or
start updating their Router/Switch Firmware!

Aerohive - http://www.aerohive.com/products/software-management/bonjour-gateway

Cisco / Meraki - https://meraki.cisco.com/technologies/bonjour-gateway

RUCKUS - https://support.ruckuswireless.com/answers/000002612 (Ruckus ZoneFlex 9.7 release or higher)

Lantronix - http://www.lantronix.com/it-management/xprintserver/xprintserver.html