You almost certainly have the object "Any" being utilized in the source/destination of rules invoking applications and/or categories. Check all of these rules, the source should be your internal networks, and the destination in all these rules should be object "Internet". Even having one rule with applications/categories and an Any in either source and/or destination can cause the effect you are observing.
Attend my Gateway Performance Optimization R81.20 course
CET (Europe) Timezone Course Scheduled for July 1-2