One user reported strange issue, they are prompted for Auto-discover Settings but not for their mailbox rather getting propts for another user.

Can anybody guide me where to start troubleshooting the problem. Environment is Exchnage 2010 Sp1 windows server 2008R2

Try creating a second outlook profile on the users workstation (Through control panel--> Mail). 

I have had instances where one user (User 1) had access to another users mailbox (User 2) and had either folders and calendars opened in their (User 1's) outlook from the other user.  The other user (User 2) changes roles where the original user (User 1) no longer had access to the mailbox.  User 1 was getting autodiscover prompts because they couldn't access User 2's mailbox.

Even though we removed the shared folder/calendar on User 1's outlook, the Outlook profile would still try to connect to User 2's mailbox.

Another case we had was where the helpdesk manager kept getting autodiscover pop up's.  I did some HTTP logging using Fiddler and found that Outlook was trying to connect to an old shared mailbox that was deleted a while back.

Both cases, recreating the Outlook profile fixed the issue.  Using Fiddler to look at the HTTP traffic should tell you what Outlook is trying to look for when it kicks off autodiscover.