Without more detail on what you're seeing in your playlists that make it appear not random, it's hard to tell you exactly what you might do to remedy it. I'm guessing, though, that you're experiencing the same thing that myself and others have had, which is that iTunes seems to play the same songs in the same order, or repeats some songs a lot while not playing the others at all. There are two main answers to these problems.
For the first, that iTunes seems to play the same songs in the same order, the answer is that the lists are randomized only whenever iTunes is restarted. So if you randomize a playlist and go back to it without restarting iTunes, you will find the songs are still in the same order. See this question over on AskDifferent for more details.
In the second possibility, that the same songs keep coming up while others seem to get no play time at all, it is especially evident if you have a large playlist. After resetting my playlist counters and then playing the same playlist for a few days, I noted that some songs had been played 3-4 times while hundreds of others had no plays. Apparently, Apple automatically weights the songs you play as more likely to be played again when in a random list. Unfortunately, this means that after it has played 20-30 songs, those become the ones it thinks you want to hear most. Resetting the play counter resets this, but you'd have to do it pretty frequently. The workaround that I have is I make a smart playlist and tell it not to include anything that has played in the last 3 days (you can extend that depending on how much you listen and how big your playlist is). This evens out the plays considerably. It may not be perfect, but to me it has made it so I don't notice repeating songs anymore.