By improving a known construction, Hsien-Chih Chang [gives a family][1] of $n$-state NFAs $A_n$ for which the shortest word witnessing non-universality has length $2^{(1/5-o(1))n}$, and even to $2^{(1/3-o(1))n}$. This improves upon the previously known bound of $2^{(1/75-o(1))n}$ given in by Ellul et al. (2005).


References:
K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)


  [1]: http://cstheory.stackexchange.com/questions/3496/conditions-for-nfa-universality