Cached mode is the best for speed, especially since you aren't using a "local" server. It might work if you turn off cached mode... but that would only be a workaround - it won't tell us what needs to be done to fix it. I'm not even sure that it gives us a hint of what might be the problem.
I'm assuming rules worked fine before you upgraded...
If you are using the same data file (ost) as you used with your old version of outlook, I would suggest deleting it and letting outlook rebuild it. Another option is to export your runs, delete them, and then import. If you have a lot of rules moving mail, they may need to be 'repointed' to the folders...
Being the lazy type with a fast internet connection and a small ost, I would delete the ost and let Outlook rebuild it - IF the profile was used in an older version of Outlook. (It's sad that 2 GB OST is considered small these days.
) If Outlook 2013 made the ost, I'd try the cleanrules switch first.
If you made a new profile in Outlook 2013, then export your rules for backup, close Outlook and restart with the /cleanrules switch. Test a new rule then import the old ones.
To use a switch, close Outlook. Press Windows key + R to open the Run command. Type or paste the following in the field and press ok:
outlook.exe /cleanrules
How to use Outlook's Command Line Switches - Slipstick Systems