For the record, the algorithm works just fine on this problem. Here's a simple python script that sets up the transfer matrix and finds the eigenvalues/eigenvectors:

zach-linear-3-sat.py

from itertools import *
import string
from numpy import *
from scipy import *
from scipy.linalg import *

#Script for setting up transfer matrix describing the evolution of diagonal
#elements of the density matrix given a list of three variable clauses.
#
#The Transfer matrix maps the vector of state populations (diagonal elements of
#the density matrix) before and after a SATDEC operation:
# v'=T.v
#where v is the vector of state populations before SATDEC and v' the vector of state populations afterward.
#
#T is in general asymmetric, and detailed balance applies: Sum_{i}T_{ij}=1 for all j.
#
#States are indexed by the value of each bit using binary ordering. Thus, FFF=0 and TTT=7.
#Each clause is specified by the bit numbers being addressed, the value
#of those bits which corresponds to failing the clause, and the decimation
#weight (fraction of original state population which is transferred away due to
#failing the clause). Thus, decimating clause ("a or b or c") with weight 0.1 is written as ["FFF", [0,1,2], .1]
# since a=F, b=F, c=F fails the clause, a, b, and c are variables 0,1, and 2 respectively, and 0.1 is the decimation weight.
#
#The Transfer matrix for a list of multiple clauses is the product of the transfer matrices for the individual clauses.

################################################################################

#dictionary mapping letters to variable number
letterdict=dict(zip(string.ascii_lowercase, [ord(c)%32-1 for c in string.ascii_lowercase]))

#dictionary mapping True/False strings to the transition matrix index
#index given by binary ordering where F=0 and T=1
def keydict(n):
    retdict={}
    invretdict={}
    tmpdict=dict()
    if n==1:
        retdict={'F':0, 'T':1}
        invretdict={0:'F', 1:'T'}
    else:
        tmpdict, invtmpdict=keydict(n-1)
        retdict={}
        invretdict={}
    for s,v in tmpdict.items():
        sp='F'+s
        vp=v
        retdict[sp]=vp
        invretdict[vp]=sp
        spp='T'+s
        vpp=v+2**(n-1)
        retdict[spp]=vpp
        invretdict[vpp]=spp
    return retdict, invretdict

#flip character between T and F, with 0 as an error value
def charflip(c):
    retc='0'
    if c=='T':
        retc='F'
    if c=='F':
        retc='T'
    return retc

#flip the nth character of a string between T and F
def stringflip(s, n):
    sl=list(s)
    sl[n]=charflip(sl[n])
    rets="".join(sl)
    return rets

#find strings where specified variables [v0, v1, v2] are equal to a three letter string
def matchitems(s, indxs):
    return filter(lambda x:(x[0][0]==s[0] and x[0][1]==s[1] and x[0][2]==s[2]),kd.items())

#depopulating one string populates strings which differ from that string by flipping the value of one of the three variables
#given the string and the set of variables, return the strings corresponding to the newly populated states
def newstates(s, indxs):
    s0=stringflip(s,indxs[0])
    s1=stringflip(s,indxs[1])
    s2=stringflip(s,indxs[2])
    return [s0,s1,s2]

#set up the transfer matrix given a set of clauses
#transfer matrix for a list of clauses is the product of the transfer matrices for the individual clauses
def tmatrixsetup(clist):
    retarray=identity(2**nbits)
    for c in clist:
        ctmat=tmat_clause(c)
        retarray=dot(ctmat,retarray)
    return retarray

#transfer matrix for a single clause
def tmat_clause(c):
    retarray=identity(2**nbits)
    s,indxs, wt=c
    mi=matchitems(s,indxs)
    for m in mi:
        ms, mindx=m
        ns=newstates(ms,indxs)
        si=kd[ms]
        for sp in ns:
            spi=kd[sp]
            retarray[si,si]-=wt
            retarray[spi,si]+=wt
    return retarray

################################################################################
#routines for processing the different way of specifying clauses used on web page (ie, (!a or b or c) rather than [[TFF],[0,1,2]])

#strip out connecting ' or ' strings
def clausesplit(c):
    return c.split(" or ")

#return failing string and variable numbers for a given clause
def processclause(c):
    cs=clausesplit(c)
    failstringlist=['0','0','0']
    numlist=[-1,-1,-1]
    for i in range(3):
        if cs[i][0]=='!':
            failstringlist[i]='T'
        else:
            failstringlist[i]='F'
        numlist[i]=letterdict[cs[i][-1]]
    return "".join(failstringlist), numlist

#setup tmatrix given a clause list:
#first transform to the [failing string , variable number , decimation weight] format used above, then call tmatrixsetup
def tmatrixsetup_clauselist(clist, wtlist):
    newclist=[]
    for i in range(len(clist)):
        failstr, varnums=processclause(clist[i])
        print("failstr, varnums\t"+str(i)+"\t"+failstr+"\t"+str(varnums))
        newclist.append([failstr, varnums, wtlist[i]])
    print(str(newclist))
    return tmatrixsetup(newclist)

################################################################################

#print eval and corresponding evec
def printevec(evals, evecs, i=0):
    print("eval, evec "+str(i)+"\t"+str(evals[i])+"\n"+str(evecs[:,i])+"\n")

################################################################################
##Simple example: 3 bits, one clause decimates every state except 'TTT' (worked example in paper)
#nbits=3
#
#kd, invkd=keydict(nbits)
#print(kd)
#
###make sure state identification code is working by depopulating 'TTT' and populating alternatives
##indxs=[0,1,2]
##mi=matchitems('TTT',indxs)
##
##for i in mi:
## s,indx=i
## ns=newstates(s,indxs)
## print("s, ns\t"+str(s)+", "+str(ns))
## print("keys "+str(kd[s])+", "+str(kd[ns[0]])+", "+str(kd[ns[1]])+", "+ str(kd[ns[2]]))
#
#clist=[['FFF',[0,1,2], .1],
# ['FFT',[0,1,2], .1],
# ['FTF',[0,1,2], .1],
# ['FTT',[0,1,2], .1],
# ['TFF',[0,1,2], .1],
# ['TFT',[0,1,2], .1],
# ['TTF',[0,1,2], .1] ]
#tmat=tmatrixsetup(clist)
#print(tmat)
#
#evals, evecs=eig(tmat)
#print(evals)


#################################################################################
nbits=8

#calculate key dictionary and its inverse, so that we can map strings to indexes in the transfer matrix
kd, invkd=keydict(nbits)
print(kd)
print(invkd)

clausestrings= ["!a or b or c",
"!a or b or !c",
"!a or !b or c",
"!a or !b or !c",
"a or !b or !c",
"a or !b or c",
"a or b or !c",
"b or c or !d",
"c or d or !e",
"d or e or !f",
"e or f or !g",
"f or g or !h",
"!a or !b or d",
"!a or b or d",
"a or !b or d",
"!a or !b or e",
"!a or b or e",
"a or !b or e",
"!a or !b or f",
"!a or b or f",
"a or !b or f",
"!a or !b or g",
"!a or b or g",
"a or !b or g",
"!a or !b or h",
"!a or b or h",
"a or !b or h"]

#test: add a clause which makes the clause unsolvable
#this should yield a single eigenvector with eigenvalue 1; the quasistationary eigendistribution
#is now a stationary eigendistribution
#clausestrings.append("a or c or e")

wt=.1
wts=ones(len(clausestrings))*wt
tmat=tmatrixsetup_clauselist(clausestrings, wts)
evals, evecs=eig(tmat)

#print eigenvalues
print("evals\n"+str(evals))

#print zeroth eigenvalue/eigenvector pair
#printevec(evals, evecs,0)

#######################################################################
#######################################################################