Error over fancy permalinks not being detected?

I’ve been playing around with the W3 Cache Plugin and also WP Super Cache Plugin

I first enabled W3, then disabled it and enabled WP Cache to see which one worked better for me.

I ended up disabling WP Super Cache and re-enabling W3 Cache

But now I’m seeing this error message at the top of my dashboard:

The required directives for fancy permalinks could not be detected, please confirm they are available: Creating and editing

What is causing this and how do I fix it?

Thank you!