The biggest challenge is a random level generation that works and doesn't get the player stuck somewhere (which would happen if it's just perlin, for instance).
One way to overcome this is to allow the player to destroy the environment, so if they do get stuck, they can get out of the situation.
Big guns which blow up the rock, or whatever your platforms are made of, or bombs, could help to this end. It will make implementation of the random terrain much less painful. So, if you include a mechanic like that, just make sure it works well with your theme.