session collistion, try to disable reverse proxy if you have any like varnish, remove SID from url and toggle the settings in system->config->web->seccion validation settings
I dont think we have a reverse proxy,  I dont have anything like varnish installed.
The SID is required because we have 3 store views.  Would turning this off stop users from being able to switch stores easilly?
I believe this issue is also related;
The checkout cart:  Is remembering only 1 setting/country,
So if you change from USA to Canada, it keeps the USA shipping method (for logged out users only)
When someone is logged in; theres no issues with shopping cart, no issues with checkout.
It seems to be only for logged-out users.
______________________________
Some others metioned its 1 of 2 things wrong:  Cookies or Session issue - Heres some settings
______________________________
-Persistent Shopping Cart
Enable: Yes
Lifetime:   31536000
Enable Remeber Me:  Yes
Remeber Me Deafult Value:  Yes
Clear Persistence on Logout:  No
Persist Shopping Cart:   Yes
System -> Config -> Web
Session Cookie Management:
Cookie Lifetime; 3600
Cookie Path;  BLANK
Cookie Domian; BLANK
Use HTTP only:  NO
Cookie Restriction Mode; NO
Session Validation Settings:
All 4 validate set to NO
Use SID on Frontend:  NO
public_html/app/code/local/Mage/Core/Model/Session/Abstract/Varien.php
           // 'domain'   => $cookie->getConfigDomain(),
           // 'secure'   => $cookie->isSecure(),
           // 'httponly' => $cookie->getHttponly()---the below code from Varien.php has (the above code) commented out. Because if its not, admin login, and userlogin dont work.
class Mage_Core_Model_Session_Abstract_Varien extends Varien_Object
{
    const VALIDATOR_KEY                         = '_session_validator_data';
    const VALIDATOR_HTTP_USER_AGENT_KEY         = 'http_user_agent';
    const VALIDATOR_HTTP_X_FORVARDED_FOR_KEY    = 'http_x_forwarded_for';
    const VALIDATOR_HTTP_VIA_KEY                = 'http_via';
    const VALIDATOR_REMOTE_ADDR_KEY             = 'remote_addr';
    /**
     * Configure and start session
     *
     * @param string $sessionName
     * @return Mage_Core_Model_Session_Abstract_Varien
     */
    public function start($sessionName=null)
    {
        if (isset($_SESSION) && !$this->getSkipEmptySessionCheck()) {
            return $this;
        }
        // getSessionSaveMethod has to return correct version of handler in any case
        $moduleName = $this->getSessionSaveMethod();
        switch ($moduleName) {
            /**
             * backward compatibility with db argument (option is @deprecated after 1.12.0.2)
             */
            case 'db':
                $moduleName = 'user';
                /* @var $sessionResource Mage_Core_Model_Resource_Session */
                $sessionResource = Mage::getResourceSingleton('core/session');
                $sessionResource->setSaveHandler();
                break;
            case 'user':
                // getSessionSavePath represents static function for custom session handler setup
                call_user_func($this->getSessionSavePath());
                break;
            case 'files':
                //don't change path if it's not writable
                if (!is_writable($this->getSessionSavePath())) {
                    break;
                }
            default:
                session_save_path($this->getSessionSavePath());
                break;
        }
        session_module_name($moduleName);
        $cookie = $this->getCookie();
        if (Mage::app()->getStore()->isAdmin()) {
            $sessionMaxLifetime = Mage_Core_Model_Resource_Session::SEESION_MAX_COOKIE_LIFETIME;
            $adminSessionLifetime = (int)Mage::getStoreConfig('admin/security/session_cookie_lifetime');
            if ($adminSessionLifetime > $sessionMaxLifetime) {
                $adminSessionLifetime = $sessionMaxLifetime;
            }
            if ($adminSessionLifetime > 60) {
                $cookie->setLifetime($adminSessionLifetime);
            }
        }
        // session cookie params
        $cookieParams = array(
            'lifetime' => $cookie->getLifetime(),
            'path'     => $cookie->getPath(),
           // 'domain'   => $cookie->getConfigDomain(),
           // 'secure'   => $cookie->isSecure(),
           // 'httponly' => $cookie->getHttponly()
        );
.HTACCESS Settings
<IfModule mod_expires.c> ExpiresActive On ExpiresByType image/jpg "access 1 month" ExpiresByType image/jpeg "access 1 month" ExpiresByType image/gif "access 1 month" ExpiresByType image/png "access 1 month" ExpiresByType text/css "access 1 month" ExpiresByType text/html "access 1 month" ExpiresByType application/pdf "access 1 month" ExpiresByType text/x-javascript "access 1 month" ExpiresByType application/x-shockwave-flash "access 1 month" ExpiresByType application/javascript "access plus 1 year" ExpiresByType image/x-icon "access 1 year" ExpiresByType font/truetype "access plus 1 month" ExpiresByType font/opentype "access plus 1 month" ExpiresByType application/x-font-woff "access plus 1 month" ExpiresByType image/svg+xml "access plus 1 month" ExpiresByType application/vnd.ms-fontobject "access plus 1 month" ExpiresDefault A0 </IfModule>
this proably requires someone to look into yur server, but if you have to comment that 3 lines to make magento work, there must be something wrong with your cookie settings.