Comments only viewable by the one who posted it

I’ve installed WordPress a few days ago and everything is working fine except the following problem.

When any person whom is not a registered user posts a comment, the form will work and the comment will seem to get posted. They can see the comment posted on the page, but the tally will not be updated.

But anyone else, whether registed/unregistered/admin, cannot even see that person’s comment at all.

This happens for any unregistered user; the only person who can see their comments are themselves. For registered users it appears to be working correctly – comments by registered users appear to everyone and the tally is correctly incremented as well.

Some info
-Using latest version of WordPress.
-I’m not using any plugins that mess with comments (eg Spam Karma)
-It is not related to the theme; the problem occurs with any theme including default.

I’m assuming it must be related to cookies. eg I can post an unregistered comment with one browser and be able to view it fine, then take a look in another browser and the comment is not there.