I made some changes to avoid the most obvious problems. I removed one reference to krbV and re-raised some exceptions to show what actually gets wrong.

diff --git a/cli/koji b/cli/koji
index d1d70c5..1e80ee2 100755
--- a/cli/koji
+++ b/cli/koji
@@ -7219,8 +7219,6 @@ def activate_session(session):
                 session.krb_login(principal=options.principal, keytab=options.keytab, proxyuser=options.runas)
             else:
                 session.krb_login(proxyuser=options.runas)
-        except krbV.Krb5Error, e:
-            error(_("Kerberos authentication failed: %s (%s)") % (e.args[1], e.args[0]))
         except socket.error, e:
             warn(_("Could not connect to Kerberos authentication service: %s") % e.args[1])
     if not options.noauth and options.authtype != "noauth" and not session.logged_in:
diff --git a/koji/__init__.py b/koji/__init__.py
index ed57965..17565c4 100644
--- a/koji/__init__.py
+++ b/koji/__init__.py
@@ -2049,7 +2049,7 @@ class ClientSession(object):
                 if self.gssapi_login(proxyuser=proxyuser):
                     return True
             except:
-                pass
+                raise
         if not krbV:
             raise exceptions.ImportError(
@@ -2157,6 +2157,7 @@ class ClientSession(object):
             except:
                 # Auth with https didn't work. Restore for the next attempt.
                 self.baseurl = old_baseurl
+                raise
         finally:
             self.opts = old_opts
         if not sinfo:

But the result isn't that great anyway.

$ PYTHONPATH=. python2.7 cli/koji -d moshimoshi
Warning: Could not install krbV module. Kerberos support will be disabled.
2017-01-16 23:58:22,436 [DEBUG] koji: Opening new requests session
2017-01-16 23:58:22,437 [DEBUG] koji: Opening new requests session
https://koji.fedoraproject.org/kojihub/ssllogin
2017-01-16 23:58:23,557 [DEBUG] koji: Opening new requests session
Traceback (most recent call last):
  File "cli/koji", line 7250, in <module>
    rv = locals()[command].__call__(options, session, args)
  File "cli/koji", line 7032, in handle_moshimoshi
    activate_session(session)
  File "cli/koji", line 7221, in activate_session
    session.krb_login(proxyuser=options.runas)
  File "/home/pavlix/src/koji/koji/__init__.py", line 2049, in krb_login
    if self.gssapi_login(proxyuser=proxyuser):
  File "/home/pavlix/src/koji/koji/__init__.py", line 2156, in gssapi_login
    sinfo = self._callMethod('sslLogin', [proxyuser], retry=False)
  File "/home/pavlix/src/koji/koji/__init__.py", line 2363, in _callMethod
    return self._sendCall(handler, headers, request)
  File "/home/pavlix/src/koji/koji/__init__.py", line 2277, in _sendCall
    return self._sendOneCall(handler, headers, request)
  File "/home/pavlix/src/koji/koji/__init__.py", line 2322, in _sendOneCall
    r = self.rsession.post(handler, **callopts)
  File "/usr/lib64/python2.7/site-packages/requests/sessions.py", line 522, in post
    return self.request('POST', url, data=data, json=json, **kwargs)
  File "/usr/lib64/python2.7/site-packages/requests/sessions.py", line 475, in request
    resp = self.send(prep, **send_kwargs)
  File "/usr/lib64/python2.7/site-packages/requests/sessions.py", line 602, in send
    r = dispatch_hook('response', hooks, r, **kwargs)
  File "/usr/lib64/python2.7/site-packages/requests/hooks.py", line 31, in dispatch_hook
    _hook_data = hook(hook_data, **kwargs)
  File "/usr/lib64/python2.7/site-packages/requests_kerberos/kerberos_.py", line 287, in handle_response
    return self.handle_response(_r, num_401s=num_401s, **kwargs)
  File "/usr/lib64/python2.7/site-packages/requests_kerberos/kerberos_.py", line 294, in handle_response
    _r = self.handle_other(response)
  File "/usr/lib64/python2.7/site-packages/requests_kerberos/kerberos_.py", line 217, in handle_other
    "{0}".format(response))
requests_kerberos.exceptions.MutualAuthenticationError: Unable to authenticate <Response [200]>

I also tried without the above change with both python-krbV and requests-kerberos installed and then apparently Kerberos works using python-krbV and not requests-kerberos. Basically whatever I'm doing, I cannot use the requests-kerberos integration at all.

This implies that the server you're hitting does not support GSSPAPI or you're being man in the middle'd.
What is your /etc/koji.conf and ~/.koji/config like?

Also, what does "dig koji.fedoraproject.org" return?

This implies that the server you're hitting does not support GSSPAPI or you're being man in the middle'd.

I expect all sorts of problems but when accessing from RH network to the official Fedora infrastructure I do not expect any of the above issues.

What is your /etc/koji.conf and ~/.koji/config like?

;; ANSWER SECTION:
koji.fedoraproject.org. 122 IN  A   209.132.181.16
koji.fedoraproject.org. 122 IN  A   209.132.181.15
;; Query time: 36 msec
;; SERVER: 10.38.5.26#53(10.38.5.26)

This implies that the server you're hitting does not support GSSPAPI or you're being man in the middle'd.
What is your /etc/koji.conf and ~/.koji/config like?

$ cat /etc/koji.conf
[koji]
;configuration for koji cli tool
;url of XMLRPC server
server = https://koji.fedoraproject.org/kojihub
;url of web interface
weburl = https://koji.fedoraproject.org/koji
;url of package download site
topurl = https://kojipkgs.fedoraproject.org/
;path to the koji top directory
;topdir = /mnt/koji
authtype = kerberos
krb_rdns = false
$ cat ~/.koji/config
cat: /home/pavlix/.koji/config: No such file or directory

@puiterwijk Have you verified the current git master actually works for you?

We've touched this issue in few more bugs (#280, #249) - it really doesn't do what it should. I can make gssapi working only if I use HTTPKerberosAuth(mutual_authentication=DISABLED) which is something we don't want. Looking more deeper now.

Hmm, it seems to be mix of problems here.

socket.getfqdn('209.132.181.16')
'proxy01.fedoraproject.org'
socket.getfqdn('koji.fedoraproject.org')
'proxy10.fedoraproject.org'

which means, that I've to setup krb_rdns = false to make it work 'somehow'. Which allows me to use krbV auth. gssapi will still be unusable as it uses mutual_authentication=REQUIRED. Would it make sense to reflect krb_rdns=false as mutual_authentication=DISABLED?

See https://fedorahosted.org/koji/ticket/328

Meanwhile, just to fix traceback #289

So, this is a problem in python-kerberos. It is not validating with the same name as it initiates for.
You can work around this by setting rdns=false in [libdefaults] of /etc/krb5.conf

I would say that setting mutual_authentication=DISABLED is definitely not something we'd want to do.

Ah, I was not aware about that config option. It solved problem for me.

Another workaround that is purely in koji is to in koji/init.py, line 2151 (self.opts['auth'] = HTTPKerberosAuth()), add a new line "self.opts['auth'].hostname_override = 'proxy01.fedoraproject.org'".

That will make it initiate the GSSAPI context for one specific proxy, which will just work.

As said though, this is a workaround. The underlying problem is that python-kerberos does the Init step agaisnt a different principal (the proxy01.fedoraproject.org it ends up with due to rdns) than it validates the hostname for. I'll take this up with the python-kerberos developer.

Ah, so python-kerberos sets the state->server_name purely based on the server name provided, and doesn't afterwards update it with the retrieved credentials.
I'll submit a patch for this.

Pure koji fix is good, as I have to modify it anyway to at least get some useful error reporting.

You can work around this by setting rdns=false in [libdefaults] of /etc/krb5.conf

Confirmed.

This build of python-kerberos fixes the problem: https://koji.fedoraproject.org/koji/taskinfo?taskID=17312083.

So with that version, neither the koji-local patch nor rdns=true are needed.
I will be working on checking with upstream to get it fixed there.

@puiterwijk Confirming, that your patch works for me. Is there some upstream issue/PR which we can reference in docs? I would add there a paragraph containing rdns=false temporary solution and link to upstream, so we know when we can delete that section.

@tkopecek I have been digging further down, and I think I'm finally onto the final cause of what's happening.
I will comment back here when I've filed a bug to the correct upstream.

@tkopecek Okay, sorry for the delay replying here.
So, short version: in all current Fedora and RHEL releases, the rdns=false is the default, which is the workaround that the krb5 maintainers in Fedora decided to use.

As such, this should only be broken if you manually changed your krb5.conf (the krb5.conf published by RH IT is broken in this regard).
As a consequence, I'm going to abandon looking further into this and my upstream patch, and my answer will be "just restore the rdns=false in your krb5.conf".

I've added warning to docs: #317

As a consequence, I'm going to abandon looking further into this and my upstream patch, and my answer will be "just restore the rdns=false in your krb5.conf".

Just an FYI, this is back in F29 (i.e. rdns=false is required to get it to work).

This issue has been migrated to Fedora Forge:
https://forge.fedoraproject.org/koji/koji/issues/288

Please continue any further discussion there.