Safari 3.1 still eats cookies, although it seems to do so much less often than 3.0. I just hit it for the first time since updating.
So what do you do when your cookies all disappear? Well, you can actually use Time Machine to restore them. The cookies are stored in ~/Library/Cookies in a single file called Cookies.plist. Trash this file, then use Time Machine to restore one from a couple hours previous.