Turn your phone off then back on. That's what I did and it worked for me. Just after you turn it back on, check in your settings to make sure the shortcuts are still saved.
I turned off "settings->ICloud->documents and data" then checked my shortcuts... some were missing some were duplicated (I assume the cloud and my device had the shortcut but sych had not worked correctly) deleted to duplicates.
BUT the others now worked.
Turned "settings->ICloud->documents and data" back on, created a new shortcut and this now worked also.
Time will tell if this "fix" is only temporary - but to me it looks like an issue with the ICloud synch