Same issue here this morning, same Veeam Backup for Microsoft 365 version.
Redid the Azure application connection, that didn’t help. Seems like Microsoft maybe changed something… (case opened)

Likewise - User & Shared Mailboxes are failing, Sites/Teams/OneDrive is all fine.

Encountered the same but only 1 tenant was affected and the rest are OK. I suggest you raise a ticket as well 

A support case was created.

Same issue here.

Same issue with my client.

Got the same issue with at least 8 of my clients.

We received a response from support with two possible ways to fix the issue.

Without quoting the entire text, here are the cliff notes.
Fix version 1 is to follow the steps in this KB:
https://www.veeam.com/kb4340

Fix version 2 (the one we chose) is to edit the C:\ProgramData\Veeam\Backup365\Config.xml
(make a backup first) and change it like so:

<Veeam>
  <Archiver>
    <Proxy SkipTeamsMessagesDataFolders="True" />
    <Server Version="7.0" ProductVersion="7.1.0.1501 P20240123" />
<...]

Here the line starting with “<Proxy” was added right after the archiver tag.
Make sure to stop the Veeam Backup for Microsoft 365 and Veeam Backup Proxy for Microsoft 365 services before editing, start them afterwards.

We can confirm #2 fixes it.

Additional notes in the case response were:
 

During the backup process, Veeam gets the folders' properties of a mailbox and the TeamsMessagesData folder is not an exclusion. In the meantime, Microsoft has restricted access via EWS to Teams message data starting on January 31, 2023. Additional information can be found here: https://devblogs.microsoft.com/microsoft365dev/restricted-access-to-microsoft-teams-data-via-ews-starts-january-31-2023/

Update:

#1 as mentiond above,  doesn’t fix the problem on our enviroment.

#2 did indeed, but that means, the Teams public channel posts will not be backed up anymore.

####

We openend also an Supportcase our Clients had the same issue. The problem seems to be the backup of the folde TeamsMessagesData. Because of new restricted access over EWS, Teams public channel posts have to backup over Teams Export APIs → KB4340: How To Configure Veeam Backup for Microsoft 365 to Use Microsoft Graph Export API for Teams

So told by the Veeam support.

Same issue here

If you enable the Graph Export API, your users need the appropriate license for it to work. It’s not entirely clear whether the standard 365 Basic/Standard/Premium licenses include it and how many hits on the API you get.

My guess is Veeam are playing it safe to make sure people aren’t negatively impacted.

Like Nakatomi, we have received a reply from support, in which the same two options for solving the problem are shown.
We can also confirm that #2 fixes the problem.

I am seeing the same problem as well. Same build. Thanks for posting the fix.

Veeam has published KB: KB4569. This is the same solution published by Nakatomi.

I do not have the Config.xml file in the C:\ProgramData\Veeam Backup365 folder.

It’s in the C:\ProgramData\Veeam\Backup365

Neither fix helps me on the two sites where I use Veeam Backup for MS365. Latest build both sites. Not good,