One thins I would suspect is a session management problem on the server.
Add the following to your add to cart page and the cart page just after the <body> tag:
echo "Session ID = ".session_id();
the session ID should stay the same on both pages. If it changes, you will need to contact the host to have them look into the session management settings on the php server.
If you continue to have problems, send a link to your add to cart page soI can investigate further..