One thing we tried in early testing, but did not pursue farther was vector quantized X (where X is MFCCs, LPC, LSF, FFT, cepstrum). Basically you use K-means to find clusters for some large number of K, then simply assign every real value (or real-valued vector) to the closest cluster. The cluster mapping becomes a codebook, and your problem goes from input vectors like [0.2, 0.7, 0.111, ...] to [0, 1, 0, ...] where the length of the vector of 0s and 1s is the number clusters K.
This is a much easier learning problem, and closely corresponds to most "bag-of-words" or word-level models. The quantization is lossy but for large enough K I do not think it would be noticeable. After all, we listen to discrete audio every day, all the time in wav format :)
To synthesize, you can either map codebook points back to the corresponding cluster center, or as most people do, map it to the cluster center with some small variance so you have a little bit of interesting variation.
I'm still not all that optimistic, frankly, but it'll be better than raw data. Some further experimentation with different encoding might be necessary.
That said, I'd put $10 bucks that just putting an FFT representation through wouldn't necessarily produce a new pop song, but it would sound uniquely spooky, I bet. If nothing else you might have something you can hook up to some speakers next Halloween and make some kids cry.