Actually, you might want to collect them with size 1 instead of deleting completely. This way Oracle has better chances to guesstimate cardinality of the columns.
Deleting the histograms did the trick! Thanks Alex!
-- Best regards, Alex Gorbachev
http://blog.oracloid.com -- //www.freelists.org/webpage/oracle-l