Seu código está funcionando para a palavra 'cat', mas não funcionará caso a palavra procura esteja na última coluna ('mkt', por exemplo) porque sua comparação está sendo feita na iteração seguinte da coluna (a primeira apenas appenda o conteúdo)

Segue uma sugestão de solução:

    crosswords=[['s','d','o','g'],['c','u','c','m'],['a','c','a','t'],['t','e','t','k']]
    word='cat'

    def find_word_vertical(cw,w):
        for i in range(len(cw)):
            wstr = ''.join([cw[j][i] for j in range(len(cw))])
            if wstr.find(w) != -1: 
                return (i,wstr.find(w))
        return (-1,-1)

    print find_word_vertical(crosswords,word)


Aproveitando, como dica, existe a lib pprint que para esse caso ajuda a visualização no interpretador:

    >>> import pprint
    >>> pprint.pprint(c)
    [['s', 'd', 'o', 'g'],
     ['c', 'u', 'c', 'm'],
     ['a', 'c', 'a', 't'],
     ['t', 'e', 't', 'k']]
    >>>