I can rsync with drush but not `drush @remote status`
The first thing to do is to ensure that the 'remote-user' in your site alias is the same user that you use when you log in to the site.

The next thing to check is whether or not drush is on your $PATH on the remote site.  You have probably set this up explicitly in a .bashrc file, since it is working when you log in locally.  However, often, .bashrc files exit early when called in non-interactive mode, as Drush does.

Perhaps the easiest way to get around this is to figure out what the correct full path to the drush script is, and set '%drush-script' in the 'path-aliases' of your site alias to point at the correct executable.  See example.aliases.drushrc.php.

UPDATE: Use '%drush-script', not '%drush'.

'remote-user' is the user that Drush will use to log in via ssh. It should be a user that has permission to use Drush. Some people use the webserver user for this, but if you have a separate web admin user, that would be a preferable choice.