Send RSA Public Key in Java to PHP server

I'm having trouble trying to convert a Java generated RSA Public KEY to string format so I can use it on the PHP side. I tried converting it to string but the encryption fails on the PHP side. I generate a public Key in Java like this:

KeyPairGenerator k = KeyPairGenerator.getInstance("RSA");
k.initialize(1024);
KeyPair kp = k.genKeyPair();
PublicKey publicKey = kp.getPublic();
PrivateKey privateKey = kp.getPrivate();

and the PublicKey when outputted to String looks something like this:

RSA Public Key
    modulus: eded852d98899fd083b6b989cbdbb41c0cf604ccdc3c4b46a6e3bdf92be898db1c53133dba4fcbc3bd7e8934b7b212856146169858ef2177e9c04c995d4fb61f9957eb6ff61a1183de03e5459ecbae7d1196778be844127fd7e80668b57037cab7a3e56c02cb881c3fb2aaddd47e5cae49c14582be01722cfa5352d9bdc97a37
    public exponent: 10001

I then encode this PublicKey like this:

byte[] pKbytes = Base64.encode(publicKey.getEncoded(), 0);
        String pK = new String(pKbytes);
        String pubKey = "-----BEGIN PUBLIC KEY-----\n" + pK + "-----END PUBLIC KEY-----\n";

and that outputted looks something like this:

-----BEGIN PUBLIC KEY-----
    MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDt7YUtmImf0
    IO2uYnL27QcDPYEzNw8S0am4735
    K+iY2xxTEz26T8vDvX6JNLeyEoVhRhaYWO8hd+nATJldT7Yf
    mVfrb/YaEYPeA+VFnsuufRGWd4vo
    RBJ/1+gGaLVwN8q3o+VsAsuIHD+yqt3UflyuScFFgr4Bciz
    6U1LZvcl6NwIDAQAB
    -----END PUBLIC KEY-----

which looks similar to the format I have on the PHP side. Encoding it using Base64 gives the final format I intend for the key String.

LS0tLS1CRUdJTiBQVUJMSUMgS0VZLS0tLS1NSUdmTUEwR0NTcUdTSWIzRFFFQkFRVUFBNEdOQURD
 QmlRS0JnUUR0N1lVdG1JbWYwSU8ydVluTDI3UWNEUFlFek53OFMwYW00NzM1SytpWTJ4eFRFejI2
    VDh2RHZYNkpOTGV5RW9WaFJoYVlXTzhoZCtuQVRKbGRUN1lmbVZmcmIvWWFFWVBlQStWRm5zdXVm
    UkdXZDR2b1JCSi8xK2dHYUxWd044cTNvK1ZzQXN1SUhEK3lxdDNVZmx5dVNjRkZncjRCY2l6NlUx
    TFp2Y2w2TndJREFRQUItLS0tLUVORCBQVUJMSUMgS0VZLS0tLS0=

After all this, the key doesn't seem to work. It encrypts a message with the key I send it but when I send it back to the Java/Android app (which contains the private key) it can't decrypt it. I've been able to do this vice-versa (i.e. take a encoded key string from PHP and convert it to a Public Key to be used by the Java/Android app) Anything I'm doing wrong here? My gut tells me I'm sending the wrong string to the PHP server

Here's what the stack Trace in Java looks like :

03-02 12:02:26.170  W/System.err﹕ java.lang.ArrayIndexOutOfBoundsException: too much data for RSA block
03-02 12:02:26.182  W/System.err﹕ at com.android.org.bouncycastle.jcajce.provider.asymmetric.rsa.CipherSpi.engineDoFinal(CipherSpi.java:464)
03-02 12:02:26.186  W/System.err﹕ at javax.crypto.Cipher.doFinal(Cipher.java:1204)
03-02 12:02:26.186  W/System.err﹕ at com.app.test.NQ.NQCrypto.decrypt(NQCrypto.java:116)

Here is how I attempt to decrypt the data in Java:

public static String decrypt(String data) throws Exception {

        Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-1AndMGF1Padding", "BC");

        cipher.init(Cipher.DECRYPT_MODE, privateKey);

        // Base 64 encode the encrypted data
        byte[] encryptedBytes = Base64.encode(cipher.doFinal(data.getBytes()), 0);

        return new String(encryptedBytes);

    }