Oh, interesting - I didn't notice the multiple-tries angle. I wonder if it's related to the files' "last opened" date - the first time I tested with TextEdit, I tried an existing file that had been sitting on my desktop for a while. In that case, TextEdit returned a "The document “<foo>” could not be opened. You don’t have permission." message.
I chalked that up to the Versions feature of OS X - it locks files that haven't been modified recently. Created a new test file, pointed the script at that, then got the results you described and went from there.
Okay, just tested with a different not-edited-in-a-while TextEdit document. Script fails when pointed at the script, then starts working if I open the file once via the Finder.
It's possible that this approach will fail if you throw a Graffle document that has been saved as a file package at it, but it appears to work correctly in the case of flat file Graffle docs. (My not-modified-recently docs on this machine appear to all be the latter type.)
Code:
set thecommand to "open Users/UserName/Desktop/FileName.graffle"
do shell script thecommand