You said you drove for a few weeks before the problem started. Air would purge out on it's own long before then.
Did you fix whatever the leak was at the reservoir? If not that can be causing the problem. The reservoir with the rad cap is part of the pressurized system and if it has a leak on that part and not pressurizing properly it can cause problems.
It sounds like you still didn't bother pressure testing the system yet? Without doing that you're wasting a lot of time guessing. Same with checking for other problems people mentioned. Just because parts are new doesn't mean it doesn't have a problem.