I'm pretty shocked that I found out now about the change thing as I read everywhere about paper wallets being secure, but no where does it state that when you spend partial amounts from your paper wallet you might actually lose it all if you don't have a change address setup.
Now my question is how does blockchain.info handle this paper wallet situation with change addresses? It's kind of scarey knowing that you coins can just disappear just because you don't know the inner workings of how transactions work.