There may be a permissions issue preventing Alfred from deleting the workflows, perhaps pasting the following (bold things) in Terminal.app:
Firstly, go to the Alfred 2 folder (this is the folder if you don't have Syncing setup):
cd Library/Application\ Support/Alfred\ 2/
Next, remove any extended attributes on Alfred's prefs:
xattr -rc Alfred.alfredpreferences
Finally, reset the permissions on Alfred's prefs:
chmod -R u+rwX,go+rX Alfred.alfredpreferences
Things should now work as expected
Cheers,
Andrew