If all other basic troubleshooting has failed (eg. try more RAM, check power supply voltage lines, clean connectors/board, VRAM etc etc), then yes I would replace the caps with tantalum replacements. I did mine a few years ago and it wasn't as bad as say doing an SE/30 nor were there as many to replace, if I recall. Some caps were a little difficult to remove though so be careful to not pull up any traces in the process.

JB