I’m using the latest versions of WP (2.5) and Simple Tags (just updated 4/12/8). The Related Posts feature in Simple Tags has never worked consistently for me. It often calls up the same 3 posts, which all happen to begin with the letter “W.” As far as I know that is all they have in common–they don’t have tags in common with each other.
Then every so often a post will have tags that make a little more sense, but not by much.
I would recommend using my Yet Another Related Posts Plugin for this. It uses a unique algorithm to give relevant results by creating a “score” for each post, considering the number of shared tags and categories but also by looking at the actual titles and content. Give it a try. 🙂