Hi, Lewishhh
how many NAV Services you have?, basically its is trying login to the Default Service where this company may be in another service.
Do the below steps
1. Give Super permission only (Remove other permission sets) without company filter and try to login if you able login select the company and login then exit.
2. now remove super permission and try your permission set without company filter and try to login if you able to login then you can restrict the company filter.
3. there is client setting on the pc you are working on and open that and see what is default service is loading if still have error login. you can access client setting below path.
C:\Users\username.Domain\AppData\Roaming\Microsoft\Microsoft Dynamics NAV\70 or 80 depending or your version .