Modern SharePoint site "Theme" suddenly changed from our Organization theme setup in Admin Portal

Thank you both for confirming and for the screenshots.

I wanted to confirm a few things in regards to what I believe you are seeing. The fix that was mentioned earlier in this thread has completed rollout late last week . That fix was specifically in regards to modern sites randomly changing colors and should no longer be occurring. 

Per the screenshot it looks as though you are specifically talking about the global navigation bar color and not the specific site collection theme. One thing to keep in mind is we did recently change this experience .

Per Message Center Post MC173542 we state "After this change takes place, OneDrive for Business, SharePoint Online, your OneDrive for Business admin center, and your SharePoint Online admin center will all be updated with a new NavBar that is aligned with the NavBar experience in Outlook.com and Office.com. The Office 365 NavBar provides shared features and capabilities that bring together OneDrive for Business, SharePoint Online, and Outlook, and simplifies your interaction with the NavBar.
 
If you’ve done work to brand OneDrive for Business and SharePoint Online, your settings will remain unchanged. If you haven’t re-branded the NavBar, you’ll notice that the default color for the apps has changed to blue.

 The Site theme selected for a specific SharePoint site through Change the look settings will no longer be applied to the navigation bar. The updated navigation bar will now be consistent as you navigate through a site, SharePoint Online and the Office 365 suite of apps (OneDrive for Business, Outlook.com, Office.com, etc.). The navigation bar theme will show the user-personalized theme, if one is selected. If there is no personalized theme, the navigation bar theme will follow either the Organizational Profile or the OneDrive for Business/SharePoint Online brand color (blue).  " 

If you do not believe this is a personalized theme setting vs our recent change please feel free to submit a support ticket and I will have our teams further investigate. I want to ensure this is a great experience and I believe we still have some confusion occurring. I apologize for any inconveniences here.