Solve the congruence using Pohlig-Hellman algorithm
You are correct in the procedure.
You need to express $x$ as $x = 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$ 
Where the $x_i$ are in $GF(2)$

First compute:
$3^{(0*(p-1)/2)} \pmod p \equiv 1$
$3^{(1*(p-1)/2)} \pmod p \equiv 65536$

So that when you'll compute 
$2^{65536/2^{i+1}} \pmod p$ you'll get either 1 (corresponding to $x_{i} = 0$) or 65536 (corresponding to $x_{i} = 1$)

For the first values of $i$ you will get only $x_i=0$, but then for $i=11$: $2^{65536/2^{12}} \pmod p\equiv 65536$ which corresponds to $x_{11}=1$

Then you need to proceed... but I just wanted to show that you don't get 0 for all $x_i$