Make sure that the replacement part is comparable in terms of ESR (equivalent series resistance), rated ripple current and rated hours. Don't use a general-purpose cap (usually rated for 1000 hrs or less, with ripple current specified at 120Hz) instead of a high-performance cap (ripple current specified at 100kHz, ESR in milliohms)
If the original capacitor was used in a high-frequency application (i.e. a capacitor on the output of a switching regulator) putting in a part that is not suited for the task will result in a severely shortened life for the cap and the need to replace it again once it blows up.
In general, going from 25V to 35V won't cause you a problem as long as the above parameters are comparable. Once you start getting above 35V, you'll find less and less high-performance capacitors available (the majority of low ESR parts tend to be 25V or lower).