Related to this, if you check the permissions in the master database, has anybody removed access from the public role? It should be there, with a tick under Grant Connect (unless that is you have given this role elevated permissions for some reason, which is unlikely).