You have to update it through the Samsung app store. There a shortcut to it in your app drawer. You have to register an account. The Samsung app store is not good with the notifications of their apps. I have both the preinstalled and play store version. There is a bit a a delay between when the Play Store and Samsung App Store gets an update, plus with the Play store version you get a reliable notification of when an update is available. You'll have to pay 9.99 for the Play Store version of PS Touch.
You should be able to trigger the update via the Samsung App Store with no additional purchase
I had issues updating the app too. It's a little annoying to update the first time. Here's what I did:
1) Close your Photoshop Touch app.
2) Find the app that is called something like Samsung apps. It will run and then the app will disappear from your app list.
3) If it's already not there or once you complete step 2, find the app called GALAXY Apps and open it. This might require an update too.
4) Do a search for Photoshop. You'll get a bunch of options there. Be careful to not choose the app that you have to purchase. Find the photoshop app that requires an update. You may have to sign up for a Samsung account to update it.
That's it, you should be able to connect after that! Hope this helps.