Pyth, 17 15 11 bytes

AQ}Ym-dH./G 

Shorter and runs in the lifespan of the universe!

Explanation

AQ}Ym-dH./G AQ Save the input into G, H. ./G Get all partitions of G. m-dH Check if the parts are in H. }Y The empty list should be present if and only if the string can be made. 

Old version

AQ&G}GsMs.pMy*HlG 

This is horrifyingly slow, but it works for my (trivially small) test cases.

Explanation

AQ&G}GsMs.pMy*HlG AQ Save the input into G, H. *HlG Repeat the list of substrings for each character of G. y Take the power set. .pM Take every permutation of each set of substrings. sMs Get a list of all the joined strings. }G Check if G is one of them. &G Make sure G is not empty.