Axials are especially hard to find current replacements for. Most all the new designs are radial (with the leads coming out of the same end). Axials the leads come out of opposing ends.
I think Vishay makes a line of current axial electrolytics (you can find them at DigiKey), but the range of values and voltage ratings is limited. You also did not mention the capacitance value.
I did a Digikey search for you for "axial electrolytic capacitors", and no parts come back at 350 V. Highest is 200 V, and all those are made by Vishay, with values from 10-100 mfd.
Parts Express has some high voltage axial electrolytics under the name "Ruby Gold". They are 350-500 V parts, from about 10 mfd up to 100 mfd:
http://www.parts-express.com/wizards/searchResults.cfm?FTR=ruby+gold+capacitor&search_type=main&WebPage_ID=3&searchFilter=ruby+gold+capacitor&x=20&y=10
Also, are you sure this is an electrolytic cap and not a film cap?
Post the capacitance!!!