OK then, I usually change the account info for the SQL Agent by going to the Services on the machine and double click on the MSSQLSERVER AND SQLSERVERAGENT; then change the account info there and you can browse to see the users in the domain. (That is for Win2K, it is similar for WinNT)
Is SQL running while you are trying to make the changes?
I am not changing SQL Agent service account. Because, I dont have any problem stopping and starting SQL Agent service. I am having problem while granting permissions to SQL user under Agent properties->Connection->SQL User Authentication. If I grant to SA login also, it is raising the same error. I hope you have understood my problem.
Error 22002: RegCreateKeyEx() returned error 5, 'Access Denied'
It doesn't look like an error because of the SQLAgent account you are using, it looks like the account that is trying to set this parameter does not have access to update the registry. Try logging into the workstation or server using Administrator and try it. NT Admin is a little much I know but there would be no question then if the same error occured.