Re: Granted that passing around little pieces of paper may look strange to the uninitiated observer
Bitcoins have value for the same reasons gold has value: both are hard to fake, available in limited supply, and facilitate trade. Bitcoins are hard to fake because there is a public ledger recording who owns them. Anyone can write updates to the ledger, but no-one else will believe them unless they have all the right digital signatures etc. That makes it almost impossible to spend coins you don't own.
However, because Bitcoin is distributed, it's possible to get two versions of the ledger, both equally valid, but different. In that case miners effectively vote for which one wins. To prevent someone stuffing the ballot box, votes are made expensive, and that's where the "proof of work" comes in: the winner is the (valid) ledger that has had the most CPU cycles spent on it.
So part of the complex number-crunching is for validating digital signatures, but most of it is for achieving consensus about ordering of updates.
The regulatory environment isn't as hostile as you seem to think it is. Both USA and UK governments consider Bitcoin to be legal, and issue guidance on how to pay taxes on profits you make with it.