This has some paths I did not expect, such as having an unauthorized request to an unimplemented method return 501 Not Implemented rather than 401 Unauthorized. Does HTTP really specify that, or does it allow either and does the flowchart just pick one of the valid ways?
So, I'm no expert but I'll offer my $.02. The difference between 5xy and 4wz type errors, it seems to me, lies in who has the problem (server vs. client, respectively) and whether or not the client should retry the request.
So, in the case of an unauthorized, unimplemented request you can only pick one response code: A 5xy unimplemented tells the client that the server is in a state where repeated requests will never be satisfied unless the server code changes. A 4wz type error tells the client that they may be able to run the request later, without changes to server code, and the request could succeed (depending on the changes made). Now, in this case, if the client gains all the permissions (so, authorized to execute any action supported by the server) the request still won't be implemented. So, the bigger issue is the (non-)implementation of the action that the client is requesting the server to perform, not the client's authorization level.
Also, a friendly reminder to everyone: authentication is not authorization.
Oh, and I haven't checked the RFCs, but this rationale makes sense to me...
A common enough recommendation that I tried to follow back when I did web development was that the core of a web service should not even be seeing the requests of users that are not allowed to access the service at all, there should be a layer before that that filters out the clearly unauthorized requests. If you do that, you cannot know whether the request is otherwise valid and might succeed later after access has been granted.
You're free to return HTTP 401 Unauthenticated if you want to. I've never tried, but I tend to suspect it will either be processed purely on the code 401, or displayed to the user somehow.
I don't know if this holds up so well for 500 Internal Server Errors, since these are usually indicative of something unexpected and needing to be fixed on the server.
Usually a client retrying a 500 error is the expected behavior, since over time that 500 error will tend to become some other status once the problem is addressed.
