Here is a somewhat different way from Johan's of looking at this
problem.  At each stage of the walk, choose a number $x$
uniformly from $[0,1]$ and then walk either a distance $x$ to the
right or $1-x$ to the left. This does not affect the probability
of becoming negative since there is still a uniform probability
of taking a step whose length belongs to the interval
$[-1,1]$. However, it does have the property that after taking
$n$ steps and choosing $0\leq x\leq 1$, the two possible
locations following the next step are the same modulo 1. Hence
the walk can be described as follows. Choose $n$ numbers
$0\lt x_1\lt \cdots\lt x_n\lt 1$, a sequence
$\epsilon=(\epsilon_1,\dots,\epsilon_n)$ of signs $\pm 1$, and a
permutation $w$ of $1,2,\dots,n$. Let the location be $y_k$ after
the $k$th step. If $\epsilon_k=1$ then step to the least real
number $y_{k+1}\equiv x_{w(k+1)}$ (mod 1), $y_{k+1}>y_k$. If
$\epsilon_k=-1$ then step to the greatest real number
$y_{k+1}\equiv x_{w(k+1)}$ (mod 1), $y_{k+1}\lt y_k$. But the
question of whether any $y_k$ is negative depends only on $\epsilon$ and
$w$, not the choice of $x_1,\dots,x_n$. There are $2^n n!$ ways
to choose $\epsilon$ and $w$. Is there a simple combinatorial
argument that the number of choices such that each $y_k>0$ is
$(2n-1)!!=1\cdot 3\cdot 5\cdots (2n-1)$? Then the probability of
success is $(2n-1)!!/2^nn! = (2n)!/4^nn!^2$.

Here is a reformulation of the combinatorial result that needs a 
simple direct proof. 

Let $f(n)$ be the number of pairs $(a_1a_2\cdots a_n,
b_1b_2\cdots b_{n-1})$ such that (a) $a_1 a_2\cdots a_n$ is a
permutation of $1,2,\dots, n$, (b) $b_i=0$ or $1$ if $a_i\lt
a_{i+1}$, (c) $b_i=0$ or $-1$ if $a_i>a_{i+1}$, and (d) $b_1
+b_2+\cdots+b_j\geq 0$ for all $1\leq j\leq n-1$. Then
$f(n)=(2n-1)!!$.

**Update.** The combinatorial result is proved bijectively by
 O. Bernardi, B. Duplantier, and P. Nadeau in Séminaire
 Lotharingien de Combinatoire, B63e (2010). In their citation [1]
 they use this result for the same purpose as above, i.e., to
 compute the probability $P_n$ (though they state the result a
 little differently).