1) Has it worked before? Could just be your internet. Give it a little time.
2) Are you in a supported country? (US, Canada, United Kingdom, France, Italy, Germany, Spain, Sweden and Singapore) If not you can't download RBN songs with a native gamertag.
3) Are there parental settings on your console (360 only)? RBN songs are technically unrated, so if there's any parental settings at all you can't download. To test, try to download a demo of an XBox Indie Game (I personally suggest Sequence, but the game you pick is irrelevant). If you can do that, it's not the settings.
4) Can you download regular RB3 DLC? Try to download one of the free songs, so you don't spend money. Could be issues contacting Harmonix's servers.