I bought an A500 for an in-law of mine several weeks ago and can confirm that the tethering option doesn't show up using the stock rom. Unfortunately, my in-law doesn't live close by, so I haven't had a chance to play with the A500 much either to see if there's a work-around.

----

For reference (will move this to a wiki somewhere if it grows large and/or useful enough):

Tablets with working Bluetooth PAN tethering out-of-the-box:
- Motorola Xoom WiFi (running stock 3.1 & 3.2 but buggy in 3.2--requiring reboots between tethers)
- Asus Transformer (running stock 3.1)
- Galaxy Tab 10.1 (running stock 3.1 with and without TouchWiz update)

Tablets without working Bluetooth PAN tethering out-of-the-box:
- Galaxy Tab (running stock rom--2.3.3?)
- Acer Iconia Tab A500 (running stock 3.1 nor 3.2)