I can't find an answer to this in BOL, or here.
I have a onepass (archive enabled) client, can I change the Storage Policy easily?
How does simpana handle building the Synthetic Full?
Or will I have to recover all the files from stubs first?
Yes, you can change the storage policy. After changing the storage policy, run a synthetic full backup to pull the data from the old SP to the new SP. Don't delete the old storage policy until the synthetic full has completed.