Is it ever a bad idea to rebuild indexes?

We have a customer database that is heavily fragmented - practically every table with more than 1000 pages has >95% fragmentation. Fill factors are set to sensible values, but page space usage is nowhere near to fill factor for most tables.

This is the result of no maintenance being performed on the database.

Rebuilding the indexes using Ola Hallengren's IndexOptimize reduces fragmentation as expected. On the existing production hardware, performance of the application improves as expected. All the metrics I normally use - client statistics on heavy queries, profiler durations, read/write stalls, application logs and user perception - indicate performance is improved.

However, a new database server backed with Intel PCIe SSDs is showing the opposite of what we expect. Highly fragmented, the application performs well. After rebuilding indexes, the application performs badly. Some operations that took ~90s now take ~6mins. However, none of the other metrics appear to indicate that the system is going slower.

Is this something anyone else has experienced?