I ran into a similar problem in 9.3.1. The fix that worked for me was to manually add the toolbox.
First, check your toolbox folder to see if the 3D Analyst Tools.tbx and Spatial Analyst Tools.tbx files exist. On my computer the toolbox files reside in C:\Program Files\ArcGIS\ArcToolbox\Toolboxes\. If the files are missing, you may need to get them from the install discs. I don't remember if it is true for 9.3.1, but some versions of ArcGIS required Arc Workstation to be installed for all toolboxes to be available. I recall this was true for the Coverage toolbox to work.
If these .tbx files are on your hard drive, add them to the Toolbox. Enable Toolbox and right-click on the "ArcToolbox" icon at the top of the toolbox pane. Select "Add Toolbox", navigate to the Toolbox folder and select the desired toolbox to add.
I hope this is a fix for your problem.