An API that connects multiple Microsoft services, enabling data access and automation across platforms
The Graph API only works with labels that are published, and as the publishing process itself might take some time, it might explain the behavior you are seeing. While waiting over a week should be sufficient, it's not uncommon for policies to get stuck and need some nudging on the backend from support.
Make sure all the labels you are interested in are part of a policy, and double-check said policy status via PowerShell (do note the DistributionStatus property only shows the actual status when querying policies individually). You can also try the diagnostics in the Purview portal (https://purview.microsoft.com/informationprotection/diagnostics).
Generally speaking, if you are performing admin operations against labels, you should use the portal or PowerShell for programmatic access. The API is not up to par on that. That said, if the changes are correctly reflected in PowerShell, they will reflect in clients as well.