A similar problem was reported with v7 in http://drupal.org/node/1335752.

I've run into it on v6, with only slight differences:
When trying to add a node to the queue, the autofill is not working - I even had to remove the "Enter the title of a node to add it to the queue" text manually.
After entering the whole title manually, the error "Please enter a valid node title." appears.
In the log, warnings appear that various .jsmin.js.gz pages are not found.

I disabled the performance option "Optimize and Minify JavaScript files", cleared the cache and re-enabled the same option. The problem then went away.

If anyone has suggestions on how to prevent this recurring, I'd be happy to hear them.