Tantalums would work fine in such an audio application, but it's generally not a good idea to use them for power supply reservior capacitors, as their low ESR (equivalent series resistance) causes high inrush currents which can cause them to fail (and sometimes explode) during power up situations.
There's no reason not to use new aluminium electrolytics to repair the A4000. They only really fail if the chemical electrolyte is a poor or unstable mixture, as seems to be the case with some of the ones used by C=.
Modern electrolytics from a decent supplier have very few long term issues. If you were concerned, you could choose a high temperature rated model which have even better long term stability.
Voltage isn't a big issue either, I think all of the capacitors of interest in the A4000D are on the 5V rail, or have a lower potential across them. Go for 16V capacitors or higher and it'll be fine. Obviously you need to pay close attention to the polarity.
Personally I prefer to use electrolytic replacement capacitors on the A4000D. If you haven't read it already, I've written a guide on the whole thing
here.
