I don't really understand why you need the restaurants permission to sing Happy Birthday, either.
That being said, I'd never go back to that restaurant.
BTW - If the restaurant had agreed to your request, they're actually opening themselves up to legal problems - They'd need a licensing agreement to legally perform the song due to copyrights. But they obviously didn't know that so it's not really an issue:
http://www.snopes.com/music/songs/birthday.asp