How can I get my cisco to talk to a 3rd-party router over Frame Relay?

You should tell your cisco to use ``encapsulation frame-relay ietf''
(instead of ``encapsulation frame-relay'') on your serial interface
that's running frame relay if your frame relay network contains a
diverse set of manufacturers' routers. The keyword ``ietf'' specifies
that your cisco will use RFC1294-compliant encapsulation, rather than
the default, RFC1490-compliant encapsulation (other products, notably
Novell MPR 2.11, use a practice sanctioned by 1294 but deemed verbotten
by 1490, namely padding of the nlpid).  If only a few routers in your
frame relay cloud require this, then you can use the default
encapsulation on everything and specify the exceptions with the
frame-relay map command:

        frame-relay map ip 10.1.2.3 56 broadcast ietf
                                                 ^^^^

(ietf stands for Internet Engineering Task Force, the body which
evaluates Standards-track RFCs; this keyword is a misnomer as both
RFC1294 and RFC1490 are ietf-approved, however 1490 is most recent and
is a Draft Standard (DS), whereas 1294 is a Proposed Standard (one step
beneath a DS), and is effectively obsolete).