Is it a Linux app serving up the printer as AirPrint compatible, or is the Printer itself AirPrint compatible?
If the first, it may require an update of whatever app you are using on the Linux machine; which I have no idea how to deal with.
If the second, then the Linux computer shouldn't matter. It's between the printer, router, and iPad. If restarting all three does not work make sure the printer is joining the wi-fi network. Also check with the printer's manufacturer to see if they've got a firmware update available.
And that's about the limit of my knowledge on the subject.