A Google search helped me to solve the problem. It seems like on some iPhone shipped with firmware 1.1.4 there is an issue with the permissions on some folders, including the one containing the cookies. These folders belong to the root user whereas when you use the iPhone you are actually logged in as a user called mobile.
To fix this, you can just open the terminal on you iPhone (it has to be jailbroken and with the Terminal application installed) and type:
chown -R mobile /var/mobile/
This will fix the permissions and cookies should work properly.