Hi,
I reproduced your scenario by publishing a web service with HTTP basic authentication and I was able to access it through a browser and also from a REST client like Postman etc., with the credentials entered.
The error HTTP 401 usually can be fixed by rectifying wrong credentials, clearing your browser's cache, fixing any errors in the URL etc., If your issue is not an intermittent occurrence and you are a partner, I would suggest you to raise a Support Case with necessary logs attached.
Hope this helps!