I found the solution (with the help of a friend: cudos!). The posterior is
$$\begin{align*}
-\log p(w|x) &= \log p(x|w) + \log p(w) + \text{const.} \\
&= \sum\limits_j \log \left( 1 + \exp(-y_j \boldsymbol{w}^\top \boldsymbol{x}_j) \right) + \sum\limits_i \frac{q_i (w_i - m_i)^2}{2} + \text{const.}'
\end{align*}$$
where the constant terms do not depend on $\boldsymbol{w}$, and with the NLL
$$\begin{align*}
-\log p(x|w) &= \sum_j \log \left[ \frac{1 + y_j}{2} \left( 1 + \mathrm{e}^{-\boldsymbol{w}^\top \boldsymbol{x}_j} \right) - \frac{1 - y_j}{2} \left( 1 + \mathrm{e}^{+\boldsymbol{w}^\top \boldsymbol{x}_j} \right) \right] \\
&= \sum\limits_j \log \left[ \frac{1 + y_j}{2} \left( 1 + \mathrm{e}^{-y_j\boldsymbol{w}^\top \boldsymbol{x}_j} \right) \right]
\end{align*}$$
for $y_j = \{-1, +1\}$ **(!)**.
Ignoring correlations, the Laplace approximation then yields
$$\begin{align*}
q_i &\leftarrow -\frac{\partial^2 \log p(w|x)}{\partial w_i^2} \\
&= q_i + \sum\limits_j x_{ij}^2 \frac{1}{1 + \mathrm{e}^{-y_j \boldsymbol{w}^\top \boldsymbol{x}_j}} \frac{1}{1 + \mathrm{e}^{+y_j \boldsymbol{w}^\top \boldsymbol{x}_j}} \\
&= q_i + \sum\limits_j x_{ij}^2 \frac{1}{1 + \mathrm{e}^{-\boldsymbol{w}^\top \boldsymbol{x}_j}} \frac{1}{1 + \mathrm{e}^{+\boldsymbol{w}^\top \boldsymbol{x}_j}} \\
&= q_i \sum\limits_j x_{ij}^2 \, p_j (1-p_j)
\end{align*}$$
with $x_{ij} = (\boldsymbol{x}_j)_i$.