Let's consider a positive charge at a point in the space. Now, if we want to bring a another positive charge to a point within the electric field of the first charge, then we have to do some work against the electrostatic force of the first charge and that work is stored as potential energy in the system.
But if we think there is a negative charge nearby, then we don't have to perform any work to bring the positive charge from infinity to that point in the electric field because here the work is done by the system which loses its potential energy. So, by definition, the potential energy of the system is zero, when the distance between two charges is infinity, and when we have brought the negative charge to that point in the electric field of the first charge, the potential energy is negative. But how can energy be negative?
In the case of earth we use this formula to determine potential energy of a particle:
$$\mathrm{P.E.}=mgh$$
Because we know that if we want to send the particle $h$ units up from earth, we have to do some work and that work is stored as potential energy.
Now, for the charges, if we hold the negative charge at earth and the positive charge as the particle then we have to perform some work to take away the positive from the negative and that work should be stored as potential energy. Then we got the maximum potential energy to be infinity and not zero, and the potential energy would never be negative in any point.