My solution (finally)!!!
Connect your iPad to your computer with your cable. Open itune, when you see your iPad in the device list on the left column, open remote on your iPad. Your library will be there. Then you can unplug everything. Since you have connected with your library once (over the cable) it will be remembered in your remote app and you will be able to use it over wifi.
Hope this will help!
If anyone is still having problems connecting iphone remote let me know as after trying many of the solutions posted i stumbled across the answwer. If like me you can not get a remote button to apperart in itunes let me know and i will retrace the simple steps i took to finally get connected.