This is a known issue with caching in Ubercart. Presently, when caching is turned on, the first time a page is viewed by an anonymous user the HTML contents will be stored in the database. This snapshot is what gets displayed next time someone views that page. This includes the cart contents in that first user's shopping cart. The solution is to simply turn off page caching for now.

We are actively seeking a more permanent solution and accepting any patches/ideas.