It always seems to happen after a major OS upgrade—no matter what the operating system... You go to print, and all the sudden you get a warning saying your printer drivers are not up-to-date or are not installed correctly.
In my case, I tried printing to my trusty and reliable Brother HL-2140 (laser printer), and I got a warning that Apple needed to update its drivers via Software Update. I let it try, but that failed. Any time I sent a new print job, the printer dialog simply told me there was an error, and the drivers were out of date.
I then deleted and added the printer in the Print & Scan system preference pane, which sometimes helps, but in this case did not. My printer is listed as being compatible with OS X 10.6 / Lion (check your own printer here), so that shouldn't be a problem. But, as is the case almost always, giving things a big konk in the head works.