GPS systems (of the type in your phone anyway) use a roughly spherical model of the Earth to calculate your position on the ground. This works very well for things that tend to be on the ground (such as people). Altitude, however, is much more difficult to calculate, as there is no "surface" with which you can assume the GPS is located.
Simplifying things somewhat, to calculate elevation, the GPS unit measures the distance from the centre of the Earth, and then applies the radius of the surface model (the sphere I mentioned in the previous paragraph), to give you the height-above-centre-of-the-Earth value at that position. The height of the ground, based on this distance from the centre of the Earth at your current location, is called the "mathematical elevation".
The mathematical elevation is around sea level in some locations, but in others it is way off. In fact, even in the places this does happen to be at sea level, this is purely coincidental.
Now... there are some tables of values that can be applied to the above calculation, to get a better idea of ground level. These tables of correctional values have been made by satellites, surveyors, and geologists. Some are more accurate than others.
You also have to take into account the density of the Earth's crust in your location, as this affects gravity, and in turn pulls the ground and sea more or less in different locations. This both affects sea level and ground level.
So, because the elevation calculated by your GPS is based on the mathematical elevation (possibly with a correction applied from a table), and combine this with the fact that the distance from the GPS satellites is around 12,500 miles (20,000 KM) and you're expecting them to figure out distances from them accurate to a few metres, the GPS uses an "error bias" towards the direction of the Earth's centre for safety reasons. This is similar to the reasoning behind the speedometer of your car having an error bias towards higher speeds (i.e. it'll say you're going faster than you really are) - with altitude you don't want planes or missiles hitting the ground unexpectedly, so the GPS tells them they're lower than they really are. This is why you see negative altitudes more often than altitudes that are too high.
As a rule of thumb, if you look at your accuracy value of your GPS at a given time, the elevation will have an accuracy error of around three times that figure.