The easy answer is that somebody can photograph you putting the cash in the machine. Cameras are pretty small these days and facial recognition is cheap.
Besides that, though, the entire mechanism of Bitcoin is one where all transactions are recorded publicly in perpetuity. It's really the polar opposite of private in that respect. It means that if your identity is ever linked to a particular bitcoin address (as in the not-so-unlikely scenario that the authorities or some other attacker are monitoring bitcoin-for-cash machines), then all transactions linked to that address can be linked to you.
I see. In hindsight my comment about “100%” anonymity was misguided. My original intuition was that a cash-bitcoin payment had to be at least “more” anonymous than the alternative of a credit card, but now I’m not so sure. Presumably tracing a credit card payment would require a court order or hacking a bank account/email, but the bitcoin scenario only needs a big database of faces which I guess you could get by crawling Facebook or something(?). Anyway, your main point about all transactions being recorded forever is well taken. Thanks for clarifying my understanding.
The other bit that people seem to neglect with BTC is that it is not immune to ordinary network analysis. Yes, it's a very clever system that creates a trustless layer of distributed storage, but it still works via IP. If you want to spend some coins, you still need to sign your transaction and submit it somehow to the network. Analysis of where that block came from (for example, by controlling the node where you submitted it, or even just simple sniffing of your connection) can correlate a physical location or IP address with a BTC address. Tor or similar measures can of course help with this, but you will probably always leak some information about your computer/OS/ISP/general physical location via things like packet timing, if you haven't accidentally leaked even more via things like forgetting to mask your MAC address.
In short, as always, it depends on your threat model. Are you trying to hide the fact that you forwarded sensitive nuclear secrets to overseas actors from a determined U.S. Government investigation? Sorry, you probably can't, at least without a bit of luck. Are you trying to fool Netflix long enough to stream latest season of Arrested Development? Probably doable.