One other place to check is Configuration - Skillsets - Call Age Preference should be set to Oldest.
If you want priority given to the oldest contact in the system, select Oldest. If you want to give priority to the first contact in the queue, select First In Queue.