Realtek driver RTL8723BE not working in Ubuntu 16.04 (kernel 4.4)
So, I figured out what the problem was. Since my machine runs on a UEFI BIOS with secured boot enabled, all the drivers that can be loaded onto the driver stack must be "signed". I think in kernel 4.4 Ubuntu, they enforced this sign verification quite strictly. That being said, all I did was to disable the secure boot from my BIOS setting (won't say this is a permanent solution) and now the wifi works like a charm.