Since AirPrint itself works with iOS 5, I'm guessing that it is the breaking of the Print n Share app that is causing your grief.
To the best of my knowledge there is no replacement for this app, and it's unlikely to be fixed. The app was 'probably' using an undocumented API to get the job done. Since Apple changes these on a regular basis (and other possible reasons) they don't want developer's using them, and have a policy against them. How Print n Share managed to escape being removed is a mystery. It's predecessor, PrintCentral did not escape notice.
Yes, all that to tell you, no solutions yet.
Short of buying an AirPrint compatible printer, using ePrint as MrLuke suggests (which is part of most HP AirPrint printers anyway), or going through the computer.