Software deployment does not apply to users when they log in to a terminal server. This is by design.
I think you will have to assign the application to the machine to deploy it via GPO, either that, or try to use loopback processing. I'm not sure if this gets round the issue or not, but it might be worth trying. Loopback processing means you can configure user settings on a GPO linked to the machine. These settings then apply to all users who log on that machine.