Debugger fails to start with confusing message when working directory does not exist

When trying to debug a program while setting a non-existing path as the working directory I get a popup with the following message:

The gdb process failed to start. Either the invoked program "/usr/bin/gdb" is missing, or you may have insufficient permissions to invoke the program.
No such file or directory

This does not hint in any way to the root cause of the issue.