Sid, sounds like your new employer does not have a public
autodiscover@company.com name set up to point to their exchange server. You will need the name of the exchange server to set up your email.
Also, sometimes with exchange login will only work with username as DOMAIN\userid where DOMAIN is whatever they set up for the company not specifically "company.com"