I have EXACTLY the same problem. The interesting thing to note is that roundcube previously worked. I can't figure out why it started some day to tell me I was refusing cookies, whatever computer and browser and login and password I would use, even if I DO accept cookies.
Well, I won't describe the whole thing again, this has already been well described above.
Here's my config, for reference :
Ubuntu 7.04 Server (kernel 2.6.21.5)
Apache 2.2.3
Roundcube SVN rev 791
PHP 5.2.1
MySQL 5.0.38