If your problem dimension is small enough, you can also try using LCON2VERT to find the vertices of your constrained region (assuming it is expected to be bounded). If the routine returns [], it will corroborate what linprog is telling you.
One other thing to be careful of, in addition to the points at Alan's documentation link, is not to use inequality constraints to express something that is really an equality constraint. For example the equality x=b can in theory be expressed using inequality constraints,
x<=b
-x<=-b
but if you do this, linprog will probably see your feasible set as empty due to machine precision issues. You should specify x=b using Aeq,beq inputs and not A,b inputs.
