I've changed my internal IP range from Class C to Class A (192.168.1.1/24 to 10.0.0.0/24 - mainly because I think it looks neater).
After reconnecting, all connected devices (a dual booted Linux/Windows Machine, and several other devices running Linux, connected via Ethernet Cable, and a Linux Laptop connected via WiFi) dealt with that flawlessly.
The only exception is my Android Phone (Oneplus Nord running OxygenOS 12.1/Android 12). It can connect to the Router via WiFi, gets assigned an IP and can communicate with internal IPs, but cannot connect to external IPs. This is only true when connected to the router directly. When connected via a Hotspot from one of the other devices in the Network, it can connect to the Internet.
I have seen other users with simmilar sounding issues, but nothing quite seemed to fully match. Does anyone have any ideas on how to fix this?