Adding to discussion: once I tried changing a corworker's gmail password just for fun (he was right beside me and doubted that I could) by just providing few ordinary information I knew about him (e-mail lists we were both subscribed to, e-mail from our boss, other coworkers, etc).
Well, I was able to change his password to a completely new one. Very concerning, not sure if it still remains that easy.