Then as soon as I switched to battery power it stopped working. It took me a while to figure out why, ie. until then I'd always had a USB cable connected to the device and my PC was forming part of the system.
The difference in capacitance was easy to measure when it's on USB - it can actually detect a hand from a few inches away. Without the USB cable the difference drops to almost nothing. I had to go from 1MHz to 8Mhz clock to be able to measure it.
Is is possible that you're looking at too large a change in F. The 'measure capacitance' references I saw were talking about measuring nF and pF variations. Is it possible that the F is changing, but your circuit isn't set to a high enough sensitivity?
Check out 'butteryfly in a jar' at youtube. (EDIT: Sorry I forgot you already referenced this one.) I'm 99% convinced it's a piezo. One guy writes 'spoiler alert - see how it works.' He plays with the butterfly, opens the lid, and shows where the batteies and switch are. And that's it. He shows how it OPERATES but not how it WORKS. So that's yet another 2:43 of my life waste that I'll never get back.

Another forum there's a buncha discussion the butterfly, capacitance, piezo, and the thread ends where someone writes 'I'll take one apart and let you know.' That was in 2011. [checking sundial [sigh]]
Given $ vs ease of design, piezo is cheap, easy and reliable.