Ben,
I have heard the same thing, but I have never seen an example. After thinking about it a bit, I came up with the following 'heuristic' reason why the structure constants should be positive for half the Chevalley generators.
Assume that it is know that simple modules for affine quiver Hecke algebras have characters given by the dual canonical basis of $U_q({n})$ (many people (not including Nakajima) expected to be true, but in light of Tsuchioka's answer shouldn't!). References for what follows are Leclerc's paper "Dual Canonical Bases, Quantum Shuffles, and $q$-characters" (EDIT (BW) This is also on the arXiv) as well as the paper of Kleshchev and Ram, and my paper with Melvin and Mondragon.
We denote the canonical and dual canonical bases $b_g$ and $b_g^*$, respectively, where $g$ runs over an appropriate index set. These bases are related by the Kashiwara form $(\cdot,\cdot)_K:U_A(n)\times U_A^*(n)\to A$ via
$$ (b_g,b_h^*)_K=\delta_{gh} $$
(above, $A=\mathbb{Z}[q,q^{-1}]$ as usual). This form is defined so that $(1,1)_K=1$ and $(f_iu,v)_K=(u,f_i'v)_K$ and $f_i'$ is Kashiwara's $q$-derivation.
Now, on the level of modules, the $q$-derivation $f_i'$ corresponds to $i$-restriction. As we have assumed $b^*_g$ is the character of a simple module, we have the $f_i'\mathcal{b}^*_g$ is the character of some module, and hence a nonnegative linear combination of dual canonical basis vectors. So now we calculate \begin{align*} f_i\mathcal{b}_g=\sum_h(f_ib_g,b^*_h)_Kb_h =\sum_h(b_g,f_i'b^*_h)_Kb_h. \end{align*} But, as we have explained, $(b_g,f_i'b^*_h)$ is nonnegative.
As I said above, this argument only works for half the generators. I haven't internalized the results of your recent paper, so I'm not sure if you've defined the biadjoint functor $e_i$ or not. If you have, then probably there should be some more information to be teased out of this line of reasoning.
