After much digging around for days, this is what I've come to understand and how I fixed my problem. Seems to be a common problem with NVIDIA drivers combined with Linux kernel updates.
Reason: NVIDIA Linux drivers have 3 main branches: 535, 550 and 570. The first one, 535, is the most stable one but might be slow to get the latest updates. While 550 can be considered as the new features branch while the 570 can be considered as the dev/latest branch.
So what happened was that when Ubuntu got the latest kernel update 6.11.0-25-generic, NVIDIA-535 didn't have the update to support the latest kernel, hence the problem.
Suggested Fixes:
You can take two paths for a fix.
Switch to an old kernel version that works and stay with it until NVIDIA Linux-535 gets support for the latest kernel version.
Switch to 550 or 570 drivers for immediate support for the latest kernel version, which NVIDIA usually provides on 550 and 570 channels.
What I actually did
I opted to wait until 535 gets the support for my kernel version and did the following,
1. Check if I've got an old kernel
That still works with the existing drivers. To list the old kernels available,
sudo grub-mkconfig | grep -iE "menuentry 'Ubuntu, with Linux" | awk '{print i++ " : "$1, $2, $3, $4, $5, $6, $7}'
Then restart with one of them to see if it works. Usually the one before the latest one works. Boot with one from the grub splash menu.
Bonus: If you have trouble getting to the the menu, change the following on /etc/defaults/grub
GRUB_TIMEOUT_STYLE=menu
GRUB_TIMEOUT=10
Bonus2: If you want to boot with the old kernel automatically,
Find the line with GRUB_DEFAULT and change its content to GRUB_DEFAULT="1>2". Note the quotation mark. Here, "1>2" means the grub will by default enter entry #1 in the first menu (Advanced Options) and then entry #2 in the 2nd menu (which points to #2 in the kernel list shown above).
Save and exit the file. Then, to apply the config file, run sudo update-grub before rebooting.
2. Full update the system
sudo apt update && sudo apt upgrade
3. Manually installing NVIDIA 535 drivers
In case the 535 drivers that are already installed had an issue or have new updates with them.
sudo apt install nvidia-driver-535
4. Reinstall the latest kernel
sudo apt install --reinstall linux-generic
5. Install the extra modules for the latest kernel
To get the network and other extras back
sudo apt install linux-modules-extra-6.11.0-25-generic
Change the kernel version accordingly (6.11.0-25-generic in my case)
Bonus: A better way to verify the problem
nvidia-smi
lsmod | grep nvidia
If nvidia-smi errors or lsmod don't show NVIDIA modules, then the GPU driver is not working correctly with the current kernel, which is exactly what happened in my case.