Using @musicamante's explanation I got my code to work. It is a bit of a workaround, but it works. Here is the fixed code:

import sys
from PySide6.QtWidgets import (
    QApplication, QMainWindow, QTableWidget, QLabel, QPushButton, QVBoxLayout, QWidget, QHBoxLayout
)
from PySide6.QtCore import Qt


class MainWindow(QMainWindow):
    def __init__(self):
        super().__init__()
        self.table = QTableWidget(5, 2)  # 5 rows, 2 columns
        self.table.setHorizontalHeaderLabels(["Column 1", "Column 2"])

        # Add a QLabel to cell (4, 0)
        label_widget = QWidget()
        layout = QHBoxLayout(label_widget)
        layout.setContentsMargins(0, 0, 0, 0)

        self.label = QLabel("Test", label_widget)
        self.table.setCellWidget(4, 0, label_widget)

        # Add a button to trigger the move
        self.button = QPushButton("Move widget")
        self.button.clicked.connect(self.move_widget)

        layout = QVBoxLayout()
        layout.addWidget(self.table)
        layout.addWidget(self.button)

        container = QWidget()
        container.setLayout(layout)
        self.setCentralWidget(container)

    def move_widget(self):
        """Move the widget from cell (4,0) to (3,0)."""
        widget = self.table.cellWidget(4, 0)

        new_label_widget = QWidget()
        layout = QHBoxLayout(new_label_widget)
        layout.setContentsMargins(0, 0, 0, 0)

        self.label.setParent(new_label_widget)

        self.table.setCellWidget(3, 0, new_label_widget)
        self.table.removeCellWidget(4, 0)
        widget.show()

        # Debug: Verify the move
        print(f"Cell (3,0) now has: {self.table.cellWidget(3, 0)}")
        print(f"Cell (4,0) now has: {self.table.cellWidget(4, 0)}")


if __name__ == "__main__":
    app = QApplication(sys.argv)
    window = MainWindow()
    window.show()
    sys.exit(app.exec())

It uses a layout as well so that the QLabel is centred, this is probably not necessary for other widgets.