Unless you are using CVX3.0 beta with SCS or ECOS solvers, I believe you are using CVX"s experimental successive approximation method. Please read http://cvxr.com/cvx/doc/advanced.html#the-successive-approximation-method for all the warnings and suggestions. Perhaps CVX"s successive approximation method is converging in some instances and not in others. If you are using CVX 2.1, your best "bet" might be use of MOSEK if available, otherwise try sedumi, sdpt3, and ECOS. Use of ECOS or SCS under CVX3.0 beta will avoid the successive approximation method and might have a better chance at success (but still see last sentence of next paragraph)..
Show us the output from the solver/CVX. Have you tried different solvers? Your coefficients span a wide range and are perhaps contributing to numerical difficulties for the solver, especially in combination with CVX's successive approximation method. Can you reformulate your problem to have a smaller range of coefficients?
You haven't told us what is changing between the instances in which it is finding a solution (if indeed it is, for which you should also show is the output) and instances in which you get a NaN solution. Perhaps some of your instances are either infeasible, or numerically appear to be infeasible to the solver.