you just do the step 2 (gather stats without the histogram), you don't need to drop anything. But of course as always, you need to test this on a dev database before deploying to prod.
Thank you once again.
Once I removed histograms from the table, it began to use the index and performance was back to the same speed as it was....very fast!
Thank you Nikolay and Justin for all the information and help provided. It increased my knowledge about this subject.