This is more dependant on your phone (ROM, kernel, tethering app, etc.) than it is on the A500. I was tethering fine between my A500 and my Sprint HTC Evo 4G until the latest Gingerbread update, where Sprint purposely broke it with the new kernel. Running a non-stock kernel solved that problem for me.
This will continue to resurface as a problem for most phones because the service providers don't want you tethering without paying the extra $ for the feature.
Samsung GALAXY Note II
Samsung GALAXY Note10.1 2014 Edition
Samsung GALAXY S III (x3)
acer Iconia A500