A lot can have happened in a year to cause performance issues. The fact that your "clean up job" did not run might or might not be the primary reason.
Before you start optimizing performance, the first thing you need to do is finding out what your biggest problem is and then address that. (Independent of the SQL Server version, or really independent of the system you are working with.)
SQL Server 2000 provides a limited set of tools you can use for this investigation. Start by tracing batch and procedure executions to see which of them take the longest and do the most reads. It is not unlikely at all that over the year the data changed in a way that a new index is now required.
If in the end you come to the conclusion that the indexes in place are the best for your workload, you can look at this "clean up job" again.
First you need to figure out (on a per table basis) if a reorganization or a rebuild is required. Reorganization usually is faster but has a smaller improvement impact. after a year of "neglect" you most likely need to execute a rebuild on all tables. See http://technet.microsoft.com/en-us/library/cc966523.aspx for more details, particularly the DBCC DBREINDEX vs. DBCC INDEXDEFRAG section.
As Shawn mentioned, each table rebuild/reorganize action requires a table lock in SQL Server 2000. To mitigate that there are two options:
Upgrade to a more modern version of SQL Server that supports online index maintenance
Clean up one table at a time and then take a significant break to allow other processes to be worked on. Depending on how many tables you have do one a night, or a few with an hour break in between each. In the following nights address other tables. You could also, each night address the 3 - 5 most fragmented tables.
DBCC SHOWCONTIG can show you how fragmented a table is. (See above link for details.)