Are you putting the username as follows?
Also make note, the above user must be a console user.
As a test try the following: On the brokerconfig.exe page change the connection radio button to "Connect using the Management Gateway" and then select update and re-try your certificate request.
I'm having the same problem and have verified and tried both suggestions and still receive the same error as the original post. I'm using the new management gateway appliance and also have a problem with about half the systems we try the on demand agent on it does not work and gets an issuser application error.
Sisyphus and Craig, this login that you're using here must be part of the LANDesk Management Suite group on the Core server and if the account is a domain account you must include the domain as Bd0g said.
You'll want to examine your IIS logs to determine if the request is hitting the brokercertificaterequest.asmx to do this open the log, scroll to the bottom and search up.
Also are you running this from a node that is on the "internet" or is it on a node that can resolve the core server locally? If you're running brokerconfig from a local machine you'll want to call the /r switch from a command line or script this will just obtain the certificate and not require credentials authentication. In your console, if you go to "Manage Scripts" in all scripts you'll find a "Create Management Gateway Client Certificate" script, you can use that as a scheduled task.