Date is looking for a timestamp as it's 2nd parameter, not a string value representing this. Updated to pass it $strtime instead.
$strtime=strtotime("2013-10-04");
$fecha=date("Y-m-d",$strtime); // <-- Unnecessary unless you want to echo the value.
echo $fecha."<br />";
$nueva_fecha=mktime(0,0,0,date("n",$strtime),date("j",$strtime)+30,date("Y",$strtime));
echo date("Y-m-d",$nueva_fecha)."<br />";
Output:
2013-10-04
2013-11-03