Bluetooth not discovering on ubuntu 21.04 - Intel 9260NGW - M.2 2230

I have a typical problem. My bluetooth is shown on as you can see in the image and it is in discovery mode. I have my cell phone next to it and it is also in discovery mode as well it is visible to nearby devices.

For some reason, my ubuntu does not recognize other bluetooth devices like my cellphone. Also my cellphone is not able to see ubuntu although it says it is power on and discoverable.

My bluetooth is Intel 9260NGW - (form factor M.2 2230) and it has wifi also. Wifi is working just fine. It is able to see all the networks and able to connect but my bluetooth has problem.

I have also done

sudo rmmod btusb
sudo modprobe btusb

sudo systemctl stop bluetooth.service 
sudo systemctl start bluetooth.service 

but it didn't solve.

Here are the output of some commands for debugging.

amarcus@amarcus-desktop:~$ sudo systemctl status bluetooth.service 
● bluetooth.service - Bluetooth service
     Loaded: loaded (/lib/systemd/system/bluetooth.service; enabled; vendor preset: enabled)
     Active: active (running) since Tue 2021-07-06 14:43:02 IST; 59s ago
       Docs: man:bluetoothd(8)
   Main PID: 940 (bluetoothd)
     Status: "Running"
      Tasks: 1 (limit: 38346)
     Memory: 1.9M
     CGroup: /system.slice/bluetooth.service
             └─940 /usr/lib/bluetooth/bluetoothd

Jul 06 14:43:02 amarcus-desktop systemd[1]: Starting Bluetooth service...
Jul 06 14:43:02 amarcus-desktop bluetoothd[940]: Bluetooth daemon 5.56
Jul 06 14:43:02 amarcus-desktop systemd[1]: Started Bluetooth service.
Jul 06 14:43:02 amarcus-desktop bluetoothd[940]: Starting SDP server
Jul 06 14:43:02 amarcus-desktop bluetoothd[940]: Bluetooth management interface 1.19 initialized
Jul 06 14:43:19 amarcus-desktop bluetoothd[940]: Endpoint registered: sender=:1.99 path=/MediaEndpoint/A2DPSink/sbc
Jul 06 14:43:19 amarcus-desktop bluetoothd[940]: Endpoint registered: sender=:1.99 path=/MediaEndpoint/A2DPSource/sbc


amarcus@amarcus-desktop:~$ lsmod | grep bt
btusb                  61440  0
btrtl                  24576  1 btusb
btbcm                  16384  1 btusb
btintel                28672  1 btusb
bluetooth             655360  43 btrtl,btintel,btbcm,bnep,btusb,rfcomm


amarcus@amarcus-desktop:~$ uname -a
Linux amarcus-desktop 5.11.0-22-generic #23-Ubuntu SMP Thu Jun 17 00:34:23 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux

amarcus@amarcus-desktop:~$ sudo rfkill list
1: phy0: Wireless LAN
    Soft blocked: no
    Hard blocked: no
2: hci0: Bluetooth
    Soft blocked: no
    Hard blocked: no

amarcus@amarcus-desktop:~$ sudo dmesg | grep Blue
[    3.307091] Bluetooth: Core ver 2.22
[    3.307115] Bluetooth: HCI device and connection manager initialized
[    3.307117] Bluetooth: HCI socket layer initialized
[    3.307119] Bluetooth: L2CAP socket layer initialized
[    3.307121] Bluetooth: SCO socket layer initialized
[    3.319768] Bluetooth: hci0: Firmware revision 0.1 build 168 week 48 2020
[    4.668924] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[    4.668928] Bluetooth: BNEP filters: protocol multicast
[    4.668931] Bluetooth: BNEP socket layer initialized
[   21.515524] Bluetooth: RFCOMM TTY layer initialized
[   21.515530] Bluetooth: RFCOMM socket layer initialized
[   21.515534] Bluetooth: RFCOMM ver 1.11


amarcus@amarcus-desktop:~$ sudo apt --only-upgrade install bluez
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
bluez is already the newest version (5.56-0ubuntu4.2).
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.