Our Galaxy is not 100% up to date, but fairly recent: it's from 03-aug-2010. Were there any recent fixes for the tool search or should our instance be recent enough?

Hmm. This should be recent enough to include the tool search and any bug fixes after we rolled it out. However, it would be nice if you could update your Galaxy instance and try again. If it still breaks, at least we're working from the current and same codebase.

Is it possible for you to update your Galaxy instance and try again?

Thanks,