It's not illegal to record a conversation between two parties. However if you share this recording with a third party (in this case Facebook) then you have to obtain the consent of the other party.
All of those apply to phone calls. In this situation we have people in a semi-public space (eg, a Pub) talking, and one person using a mobile phone to send background noise (which will include that conversation) to Facebook or Shazzam who process the noise, identify any music, and then discard the noise.
Your law would prevent people in busy offices from making any phone calls.
> It shall be an offence for a person intentionally and without lawful authority to intercept, at any place in the United Kingdom, any communication in the course of its transmission by means of—
> (a)a public postal service; or
> (b)a public telecommunication system.
EDIT: I'm not saying it's okay. I'm just asking what law is being broken.