There are two separately copyrightable elements to a sound recording, as you point out: the musical work, and the performance.
If you want to record a cover version of a song, what matters is the license you hold, if any, to the underlying musical work. The license to the recording is not relevant unless you are sampling or duplicating the recording.
The key, however, is that whoever you got the song from has the same issue. With this in mind, there are three basic scenarios:
1) The recording is released under a cc license, but the song is in the public domain. If the song is in the public domain, the recording license is irrelevant; you have the right to cover it.
2) The recording is released under a cc license, but someone other than the recording artist holds the rights to the musical work. In this case, the recording artist almost certainly does not have the right to distribute the recording under a cc license. Musical works are subject to a "mechanical license;" this means that you can record a cover version without permission, but only if you pay royalties to the composer. If you record a cover under these circumstances, both you and the person who attempted to release the item under a cc license will be liable.
3) The recording is released under a cc license by a recording artist who also holds the rights to the musical work--in other words, an original composition. In this case, the answer to your question will depend on the specific license language, and a court's interpretation of it.
The CC license defines "Licensed Material" as "the artistic or literary work, database, or other material to which the Licensor applied this Public License." Some CC licenses permit the Licensed Material to be "translated, altered, arranged, transformed, or otherwise modified in a manner requiring permission under the Copyright and Similar Rights held by the Licensor." Some don't.
The CC web site lists litigation involving their licenses, and no litigation listed there seems to address the question of whether, when a CC license is applied to a sound recording, the "Licensed Material" includes the underlying musical work. It is therefore hard to predict what a court would do; you would need an opinion from an experienced intellectual property attorney licensed to practice in your jurisdiction.
Or, on a more practical note: if you aren't sure, ask the license holder. If they give you permission, that resolves the issue.