I had the exact same problem solo mining. I would get over half rejects. I assumed that it was because the only other person on the network was getting blocks just as fast as I was and we would often mine the same block and one of us would get a reject.
I ran for an hour and got ALL rejects, even re-downloaded the block chain (just in case), same thing, all rejects