After checking my router settings, you are absolutely correct, I added a port forwarding rule for my laptop's IP, and now it is working perfectly, thanks for the response! I love you're app, and am now more than ever highly considering permanently paying for the premium version, thanks a lot!

I have the exact same problem, except the remote app has never worked for me. I'm running Linux Mint 17.1 on my laptop, and I have a OnePlus One as my phone. I have my phone and laptop on the same wifi network as the Chromecast, and I'll have a video playing through Videostream (which btw works perfectly). But whenever I try the Android remote app, it just searches and never finds Videostream. It is quite lame :(