With fewer unknowns than equations, nothing you do can "solve" the problem, because there will be normally be infinitely many solutions (if any exist). At best, you can find a completely arbitrary solution among many. The solution you obtain will be completely dependent on your start point. Change the start point, and you will find some completely different solution.
With more unknowns than equations, you will have no EXACT solution in general. At best, you will need to find a set of parameters that minimizes the sum of squares of residuals. This is what algorithms like Levenberg-Marquardt are designed to solve, and why that algorithm must be invoked. At that point, you might as well have decided to used lsqnonlin instead of fsolve, since lsqnonlin is designed to solve that class of problem anyway.
As for what else can be the problem, it tells you exactly what the problem was! You have a non-square system.
