It's possible to make a truly secure paper bitcoin wallet using Visual Cryptography.

 http://www-ti.informatik.uni-tuebingen.de/~borchert/Troja/studdiplchrist/indexEN.php

 so what you would do is put the private key(or the secret message) into the VC system, giving you two VC factors V₁ and V₂.

 obviously if these two factors, V₁ and V₂, are brought together- a secret message is revealed.

 a serial number is generated.

 V₂ is labelled with the SHA hash of this serial number.

 V₁ is simply labelled with the serial number.
 
 V₂ is given to some local official for safekeeping.  V₁, is given to the user- that is his paper wallet.  He doesnt know what the private key is, he must meet with the local official and get the other factor to reveal the key(by hashing the serial number on his note), at that moment, the funds can be released on Bitcoin, and the wallet destroyed.

 The only party CAPABLE of knowing the secrets are the creators of the two VC factors, and even this could be automated so that they have minimal ability to know.

 an online tool for printing Visual Cryptography: http://leemon.com/crypto/VisualCrypto.html

I suspect you could 'mint' some kind of paper money backed by Bitcoins using Visual Crypto.  Haven't really worked out the details.

The primary problem is the situation where someone could COPY one of the VC factors, so you couldn't easily distribute.  At the least you would need to feature a hologram/kinegram in order to prevent counterfeit.  There could be a serial number on the bill, and you could check online to see if the bill is still valid(similar to Chaum), but what is the point if it relies on an internet connection?  I would think you could make small denomination bills safely.  There is a company that does this though: http://www.bitbills.com/

-bm

Is bitbills still in business?  Another similar one is coming soon at coinverters.com

they appear to be in business.  did you follow the link?

interesting.
i think soon we can find ways to create tradable physical coins 

Error correction is a problem with this approach. QR codes for example have error correction built in and have wide support by a variety of devices and programs. You can split a private key into multiple fragments using secret sharing algos and then print each fragment together with a QR code on a separate piece of paper. This way you can recover a secret if even 30% of the QR code is damaged.

Armory already produces fragmented M of N backups. All you have to do is print QR codes along with those backup fragments. That is the alternative to VC that exists. It has numerous advantages like ECC and better hardware/software support.

Is this more of a "gee whiz look what we could do" ... or is there someone actually doing something here?

nb: bitbills have been out of business for a long time, in internet years.