This was a bit of a ridiculous error. It occurred after a PHP upgrade to 5.2.17 running under Apache with mod_php. Initially phpMyAdmin just rejected the login which clearing the browser’s cookies fixed. Following this, the error “cannot start session without errors” was produced. Sessions in PHP were working fine as other sites were setting them successfully. session.save_path in php.ini was set to /var/lib/php/session. This directory had write access from the Apache user. The problem was fixed by changing the permissions to 0777 on this directory.
I haven’t bothered to investigate the real reason behind the problem but the aforementioned permissions fix seems to have solved it. Do let me know if you figure this out.