Tags/Categories function failing randomly?

I have redesigned my WP blog, http://prettymuchamazing.com/ to include tabbed widgets on the sidebar. The widgets are powered by the Tags and Categories functions on WP.

For example, if I want a certain tab to list the 10 most recent posts filed under “Album Review”, it will via php

But what I have noticed is that randomly the tag (mostly) and category functions seem to fail. By this I mean that when the tabbed sidebar widgets call for a list of posts, nothing is outputted. Here is a pic of what it looks like when it fails: http://i34.tinypic.com/2mw8os7.png

I’ve also noticed that sometimes (also seems random) when I save a draft or even publish a post, the tags and sometimes even the categories I file the post under don’t save or publish along with it. I’m not sure if there’s a connection between the two.

Has this happened to anyone before? Is there something wrong with my WP database? Something wrong with the db connection? Does anyone have a solution? Thanks in advanced.