Yes, I had that issue too (years ago, when they first allowed deleting the Music app). I think it might not be a problem in newer cars, but my car radio only had iPod support, not iPhone, and it seemingly needed at least one song in the music library for the connectivity to work at all.
(I also have to have downloaded music... thankfully I got that U2 album ages ago, ha.)