Warning - handwaving ramblings to follow:
Firstly, how are you determining that the negatives are overexposed? - If they are being commercially printed, there is a good chance that they are being automatically brightened up to control for what the machine thinks is your underexposure. You might want to try getting a good quality scan of some of the negatives, and seeing if they really are underexposed, or if it is a printing issue.
My thought is that since the light source is moving, and is against a dark background, the shutter time does not contribute to the exposure, so you are looking at something where the only real contributor to the exposure will be your aperture.
The closer you are to the fireworks, the faster the image of the light source will be moving across your film, and the wider the aperture that you will need for a given exposure - which seems counter-intuitive.
The last time I shot fireworks (granted it was not with 35mm), I was using a 100 ASA transparency film, and I used f16, with relatively long exposures.