Hoo boy.
Hate to say it, but your BTC may be gone. When you spend coins (such as the 32 you have in one paper wallet address) you send two transactions. The first is the payment, and the second is the change. The change does not go back to the paper wallet by default, so you get a second address with 32-8-trans fees = 23.99xxx BTC.
Your paper wallet is probably empty, which is why you get that error. Hopefully you can find the change
Edit: I don't mean 8btc, but the BTC you were able to spend weeks earlier.