I've gone through various articles, but the problem still occurs.
Steps Taken:

1. Enable Remote Desktop on my Microsoft Surface Pro

2. Went into Linksys EA6500 configuration and have tried the following configurations:
a. Single Port Forwarding external: 8888 internal: 3389 Dest IP: 192.168.1.100 (Surface Pro, which I've also setup as a static IP on the router)
b. Single Port Forwarding external: 3389 internal: 3389 Dest IP: 192.168.1.100
c. Multiple Port Range 3389 - 3389 Dest IP: 192.168.1.100

3. Made sure that Windows firewall was not blocking RDP, even tried turning it off.

4. Checked Whatismyip for external IP address

5. On the RDP Android app, I added a new RDP session with the following details:
a.Entered PC Name: External IP, Username

b. Gateway: 192.168.1.1:3389 also tried Gateway: 192.168.1.1:8888

It will keep erroring out saying: "We couldn't connect to the gateway because of an error. If this keeps happening, ask your admin or tech support for help.

Error code: 0x3000008

2. b. should be correct, and 5. a. should be good as long as your surface's local IP is 192.168.1.100   The only thing I don't see mentioned is if the EA6500 has a firewall turned on and could it be blocking the connection?   If you have another PC on your local LAN, you can test the connection to the surface locally, but then use the address 192.168.1.100 instead of the external address, to see if the problem is your router, or the Surface.  If it works and external doesn't, it's the router.  

Did you already use the latest version, did you try this app with different device like PC or laptop?

https://play.google.com/store/apps/details?id=com.microsoft.rdc.android

as stated on android RDP download site from android market, I suggest you contact technical support. They have the best resources to handle your issue, at least make sure this issue not related to android RDP app

• Edited by britishdhez 3 hours 8 minutes ago

Did you already use the latest version, did you try this app with different device like PC or laptop?

https://play.google.com/store/apps/details?id=com.microsoft.rdc.android

as stated on android RDP download site from android market, I suggest you contact technical support. They have the best resources to handle your issue, at least make sure this issue not related to android RDP app

• Edited by britishdhez Wednesday, July 29, 2015 4:15 AM