Hi,
     I have created a new user and provided the password and tried logging in to SFDC. I was able to login for the very first time.Once I logout from the application and log in to SFDC from the next time it displays me an error 'Your login attempt has failed. The username or password may be incorrect, or your location or login time may be restricted. Please contact the administrator at your company for help.'

As I am the system admin and am able to login I can say that there is no downtime also.

I am sure that the password is correct and there are no login hours/ IP restrictions. 

Could any one explain why this might be happening.

Thanks,
Karthik