While it is very good at handling absurdly large numbers, some of the numbers I was using were a little too large.

If your power function is just being used for RSA, then there is no reason to be dealing with absurdly large numbers. You can have your function take the modulus (i.e. m = pq) and reduce mod m at each step. It's faster and limits the size of numbers you are working with.

Also, using trial division for primality testing? Ouch. I'd check that it's not even (if x & 1) [and possible other small primes] and use Miller-Rabin or Solovey-Strassen to test for primality. These are probabilistic tests, but a couple rounds of these will be much faster than trial division.

Edit: modular exponentiation:

def modular_exponent(base,exponent, mod):
    n = exponent
    x = 1
    power = base % mod
    while n:
        if n & 1:
            x *= power
            x %= mod
            n -= 1
        power = (power ** 2) % mod
        n >>= 1
    return x

and Miller-Rabin:

def MillerRabin(n,k=5):
'''
Performs the Miller-Rabin primality test on n to an error bound of 4^-k 
(i.e. performs the test k times). True indicates a probable prime while a 
false result indicates a definite composite number.
Inputs:
n - Number to be tested for primality
k - Error bounding parameter
Outputs:
True if n passes k rounds of the Miller-Rabin test, False otherwise
'''
import random
def innerTest(x):
    for r in xrange(2,n-1):
        x = modular_exponent(x,2,n)
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False
ks = []
d = 0
s = n-1
# Write n-1 as 2^d * s
while not s & 1:
    d += 1
    s >>= 1
while len(ks) < k:
    a = random.randint(2,n-2)
    if a in ks:
        continue
    ks.append(a)
    x = modular_exponent(a,s,n)
    if x == 1 or x == n - 1:
        continue
    if innerTest(x):
        continue
    return False
return True