I tried out Picasa's face recognition earlier this year. Initially is looked very promising and felt magical.
However after much scanning of my files I realised it was never really going to work. Even after extensive training, telling it who was who, it was still repeatedly failing to identify seemingly nearly identical shots of people as being connected. After 10 days of trying to train it the training work load was unreduced so I gave up and deleted its face database.
I'm mostly seeing that as well. The majority of photos it just isn't doing it correctly. It either doesn't detect a face at all or it thinks it is somebody else.