I haven't tried Gibson Assembly myself, but I do know the Cambridge iGEM Team in 2010 and 2011 developed a web-based tool - Gibthon \- for automatically generating primers for Gibson Assembly.
You could try running your difficult sequences through their tool to see what it suggests for primers. It apparently gives you a "value for the Gibbs free energy of the worst case secondary structure of the primer."