The following solution just worked for me. No need to turn off Documents & Data in the iCloud control panel.
You do need an older copy of the file,
~/Library/Mail/V2/MailData/SyncedSmartMailboxes.plist
because the current is basically empty, destroyed by an evil Apple mistake. I found my file in yesterday's TimeMachine backup (yay, Apple!).
It seems the file,
~/Library/Mail/V2/MailData/SyncedFilesInfo.plist
maintains a list of sync'd files.
My Steps:
1) Quit Mail
2) Deleted the final entry in the file
~/Library/Mail/V2/MailData/SyncedFilesInfo.plist
which looks like this:
<key> a bunch of stuff</key>
<dict> a bunch of stuff </dict>
3) Start mail app, and voila! the smart folders are there.
Hope it works for you!