If you have a session id in the cookie that can't be found in the database, a new session will be created automatically. If you want to destroy an existing session, use \Session::destroy().
If the session does not exist, page 2 will create a new session. And $uid will be NULL, since no value called 'userid' will exist in this new session.
This is how every session works?
What do you think you repair by deleting the cookie? When you request page 2 after that delete, you still have a new session key, and $uid will still be NULL...
And you are sure you're on the current Fuel release? There was an older release that had some issues with auto creation of new sessions (1.4 or 1.5 I think), so make sure your on the latest version.
You should ALWAYS be able to delete a cookie using setcookie() or \Cookie::delete().
If that doesn't work, you either have an entirely different problem, or your diagnosis is wrong (for example, are you sure it's the same cookie you are looking at? Fuel will re-create it immediately if it's missing).
A lot changed since 1.4, so fixing things without upgrading isn't going to be easy, and probably will take more time then upgrading to 1.7.1, and making the few changes to your app code that comes along with that (check the changelog's of 1.5, 1.6 and 1.7 before you start).