Author Permalinks working only for Admin

Hi,
I’ve a problem on my blog. I’ve around 20 authors on my blog. And in about page, I’ve Authors’ names linked to their respective the_author_posts_link();

The link works fine if disable permalinks, but its breaking for everyone other than me (admin). All other author’s permalinks are throwing a 404 error.

Can anyone help me out, as I’ve seen the same bug as resolved for Wp 2.2 at http://wordpress.org/support/topic/123433 but I’m getting the same problem on 2.5.1