You do not need to rebuild indexes after analyzing table. Try analyzing indexes also. or..
May be your queries work better in Rule based optimizer. If you delete statistics the queries will use RBO again.

Sanjay