It sounds like someone messed up. Maybe it was a ramp-release based on an inaccurate forecast; or it could have been a fueler who accidentally put too much fuel onboard. It is conceivable that the temperature went significantly above what they expected (was it particularly hot that day?).
It sounds like they were lying to the passengers, though, because they wouldn't have put all that fuel on unless there were a reason like bad weather at the destination. If this was the case, they would have been planning on that fuel weight from the beginning and they would not have been able to load all the baggage. If the weather had cleared up at the destination, they would not remove fuel, because that it more expensive than carrying the extra weight. Fuel that is removed from airplanes cannot be used again in an airplane. It must be sold on a secondary market for non-aviation purposes. ($$$)
So, if it got really hot they were telling the truth, but if not, they were lying so everyone would not start whining like a bunch of babies.
As for your 757 leaving on time, it could be because the 757 is a more capable aircraft or it could be because your airline didn't screw up the weight & balance.