Doped antiferromagnets host a vast array of physical properties and learning how to control them is one of the biggest challenges of condensed matter physics. La$_{1.7}$Sr$_{0.3}$NiO$_4$ (LSNO) is a classic example of such a material. At low temperatures holes introduced via substitution of La by Sr segregate into lines to form boundaries between magnetically ordered domains in the form of stripes. The stripes become dynamic at high temperatures, but LSNO remains insulating presumably because an interplay between magnetic correlations and electron-phonon coupling localizes charge carriers. Magnetic degrees of freedom have been extensively investigated in this system, but phonons are almost completely unexplored. We searched for electron-phonon anomalies in LSNO by inelastic neutron scattering. Giant renormalization of plane Ni-O bond-stretching modes that modulate the volume around Ni appears on entering the dynamic charge stripe phase. Other phonons are a lot less sensitive to stripe melting. Dramatic overdamping of the breathing modes indicates that dynamic stripe phase may host small polarons. We argue that this feature sets electron-phonon coupling in nickelates apart from that in cuprates where breathing phonons are not overdamped and point out remarkable similarities with the colossal magnetoresistance (CMR) manganites.