I've been playing with saving Application Data within workflow for Tridion 2011 SP1. Since the previous answers all seem to be outside the context of workflow, I thought I should contribute my findings (as it proved rather frustrating to me until I discovered what was going on) as they run counter to Nuno's suggestion to always clean uri's when saving.
My problem boiled down to this: Within an automated workflow activity, if I tried to update the value of a component's Application Data to a different value it seemed like the call to SaveApplicationData had no effect - the original value always remained. I debugged repeatedly to make sure the component tcmuri I was using for the saving & reading was the same and it always was. Enlightenment didn't come until until I cracked the DB open (bad, I know - but I just needed to see) and watched the Application Data as my application attempted to update it.
What I saw was when a component enters workflow, the system automatically creates a copy of the current version's Application Data record with a version of 0. Upon completion of workflow, this version 0 appears to become the new version. For example, if there were 3 versions when workflow began, a fourth entry would be created with version 0. When workflow finished, this version 0 would become version 4.
What caused my troubles was the fact that when I was attempting to overwrite the Application Data value for the component, the component tcmuri I would use came out of the workflow's current subject and was version-less. Therefore my save would update the latest version (NOT version 0 that was currently in workflow) and once the component came out of workflow, unchanged version 0 became the newest version (the updated version was superseded by the "new version" making it look like my change hadn't been saved). I never rolled back the component's version, but I'm guessing if I'd rolled back the latest version I would have then had my updated value...
In order to make this work in the context of workflow I had to add
-v0 to the component tcmuri when I was calling SaveApplicationData. So, Kunal's statement about SaveApplicationData not working with versioned tcmuri's is not actually correct.
I do like changes to the Application Data being tied to the workflow version - so if the process is deleted the change to the Application Data is also rolled back. It just wasn't very clear to me in the documentation how important it was to understand the relationship between versioning, workflow and Application Data.