You are right. Turning off the firewall is the easiest way to solve the issue. If the firewall is on, the laptop's wifi hotspot will activate, but the phone won't be able to connect to the hotspot since the firewall will block it.
So it is important to know if @Pl4t1num has his/her firewall on
If the firewall is on, and you want your hotspot to work with hotspot on, then follow this dedicated tutorial/guide made by zenzen after I gave my post which @applecheeks37 mentioned:
[HOW TO] Configure firewall rules for sharing internet
Then again, as @applecheeks37 said, if your firewall is off and you are still having the connection issue, then we have to dig deeper about the problem.