Does it just take awhile for workflow to recognize changes to the repository? My renaming workflows are not working when I change or create entries like my starting rules indicate they should.
No, Workflow usually starts working within a few seconds. You may want to check your Workflow Subscriber Service to make sure it's running. If it is, the next thing to check would be the Subscriber itself within the Workflow Administration Console. Check to see if the Create or Change events are even being seen by the Subscriber.
As Shelby said, you can check what's happening behind the scenes if you open the Workflow Administration console, expand the monitoring section, click subscribers, then double click the subscriber name.
This view will show you how the starting rules were evaluated for each document so you can troubleshoot more easily.
Also have a look at the Workflow Configuration Manager - Monitored Repositories and make your repository is monitored.
If your repository isn't being monitored, Workflow wont pick up any changes made to an entry.
Is it only that workflow? Other workflows are working as expected?
Double check your starting rules. It's easy to accidentally set the starting event as entry created rather than entry changed.