Hello all,
The issue has been resolved. There was another MSDE running on that machine and localhost was resolving to that and that is why it was unable to login using user created logins. Localhost was not pointing to the SQL server.
Since both(MSDE and SQL server) have sa logins and the password for sa was blank on both we didn't realise this was happening until we created the sa login with a password for sql server and then tried to login. It didn't allow us to login with sa then. That's when we realised it was looking somewhere else.