It just depends on what your reference point is. For example, as it is convention to have gravitational potential energy at an infinite distance away to be 0 joules, our calculations show GPE to be negative.
I think you need to step back and learn a bit more on classical mechanics. One can easily see that, for example, in attractive energies (example: gravitational potential), it is DEFINED that zero is at infinity, and that the gravitational potential well is defined as being negative! The same can be said about the potential that an electron has in an atom (look at the potential energy term in the Schrodinger equation). So you need to learn a bit more of what we mean by negative energy, and why it is rather arbitrary in some sense. Zz.
nouveau_riche, You are absolutely correct, and this is not a trivial issue, as several responses have implied. It's true that in Newtonian physics the zero point of energy is arbitrary. You can define it to be the energy that a particle has as infinity, or you can define it to be the energy it has at the Earth's surface, as you like. But in relativity this is not the case. In relativity the zero point of energy is absolute. A particle's gravitational potential energy is negative but can never exceed its rest mass, and so the sum is always positive. The statement you made, "anything that has positive mass must have positive energy" is known as the Positive Energy Theorem or Positive Mass Conjecture, and has been proved under rather general assumptions. See the Wikipedia article http://en.wikipedia.org/wiki/Positive_energy_theorem, or google Positive Energy Theorem and you will find many references to it.