Oops, Sorry everyone.
It's my error.
In my javascript I'm using a Jquery cookie plugin and when you set a new cookie you tell it the number of days before expiry:
$.cookie('locationid', value, { expires: 365, path: '/' });
Unfortunately I used a part of this syntax in my controller:
$cookie = new Cookie("locationid", $cookieLocation, 365, '/', null, false, false);
The problem is the third parameter is supposed to be a DateTime so while I thought I was telling it to expire in 365 days I probably created a cookie that expired almost instantly after creation.
Thanks for all the answers and time spent on your part, this is why I love SO.