Python: 591 bytes

import sys
l=list
n=len
a=[sys.stdin.readline().upper().replace('J','I') for i in (1,2)]
b=l('ABCDEFGHIKLMNOPQRSTUVWXYZ')
def z(x):
    a=0
    if x in b:
        b.remove(x)
        a=1
    return a
c=l(filter(z,a[0]))+b
d=[x for x in a[1] if x in c]
e=1
while e<n(d):
    if d[e-1]==d[e]:
        d.insert(e,'X')
    e+=1e+=2
if n(d)%2>0:
    d+='X'
def y(i):
    z=c.index(d[i])
    return z/5,z%5
x=lambda i,j:c[(i%5)*5+(j%5)]
def w(i):
    e,f=y(i)
    g,h=y(i+1)
    if e==g:
        z=x(e,f+1)+x(g,h+1)
    elif f==h:
        z=x(e+1,f)+x(g+1,h)
    else:
        z=x(e,h)+x(g,f)
    print z,
e=0
while e<n(d):
    w(e)
    e+=2
print

This uses stdin to get the key and the message in that order. I hope it's not cheating to use a flat list to store the encryption matrix, because that made working with the matrix pretty simple. Here are some example runs:

>python playfair.py
Stack Overflow
The cat crept into the crypt, crapped, and crept out again.
SI RA CA RD FM VU IC VS MO RD ZN AK EC MZ MF BC YN RD FM SV TV KB TM MY

>python playfair.py
Stack Overflow
The quick red fox jumps over the lazy brown dog.
SI OX TU KS FR GR EQ UT NH OL ER VC MO BS QZ DE VL YN FL