I know this thread is a little old now, but I came across it via Google.
I had this problem recently on a CentOS machine with VirtualMin installed. Using VirtualMin's installer script, I installed the old version (v2) of PHPMyAdmin into a domain, and then got the same error as described in this thread.
My solution? A bit weird, but basically I edited phpmyadmin/index.php, inserting:
in the next line after the opening <?php tag.
This forced the server to send a header and thus the rest of the page, which (I think) may have had the effect of setting a cookie on my machine.
I then removed the echo line and refreshed the page - it still works.
Hope that helps somebody.