I have a well for my water.and I have a strong egg smell coming from the water.normally putting bleach down the well solves the problem but didn't help this time. Any suggestions?

Sounds like you may have hydrogen sulfate gas in your well, This will make your water smell like rotten eggs. The only way I know to clear up "sulfur water" is to install a aeration tank and pump,(see image) This system will aerate the water and remove the gas. We have sulfur water in my area and that's how we deal with it. Good luck, Tom

Any plumbing work been done recently, maybe a new water heater?

No.no new work...

Does the hot and the cold both smell like rotten eggs?

Yes it does.