I had the same problem. If your power goes out, even flickers for a second, then you can not remote connect. Let me say that again, sometimes it will connect, most of the time it won't.
You can also check the Sony knowledge center that deals specifically with remote start: http://playstation.custhelp.com/cgi-bin/playstation.cfg/php/enduser/std_adp.php?p_faqid=445&p_created=1194643575&p_sid=BdT86Qpj&p_accessibility=0&p_redirect=&p_lva=&p_sp=cF9zcmNoPTEmcF9zb3J0X2J5PSZwX2dyaWRzb3J0PSZwX3Jvd19jbnQ9MzE5LDMxOSZwX3Byb2RzPSZwX2NhdHM9JnBfcHY9JnBfY3Y9JnBfc2VhcmNoX3R5cGU9YW5zd2Vycy5zZWFyY2hfbmwmcF9wYWdlPTEmcF9zZWFyY2hfdGV4dD1wc3AgcmVtb3RlIGNvbm5lY3Q*&p_li=&p_topview=1 Click on "How to use Remote Start via the Internet" and make sure you are doing it correctly.