Optimizer doesn't take statistics into account before shutdown/restart?

Hi,

Has anyone run into this kind of situation: we ran dbms_stats.gather_database_stats() because sql performance was under expectations. Nothing seemed to work as in previous incarnation of the database and large tables seemed to end in full table scans all the time - even though the queries were designed to use an index. Nothing seemed to help before we shutdown the database and started it up - after that all queries performed as they should. Are the statistics somehow not dynamically taken into account or is this a bug? This is the second time we ran into this problem.