In case it's helpful for others, I got the exact same error as this when trying to upload a file to a path that didn't yet exist. scp from shell will allow you to do this, but Net::SCP will fail with this error.
i.e.
scp "my.file" "/foo/bar/"
if /foo exists but /foo/bar/ does not, scp will create /foo/bar and put your file there (assuming permissions allow you to do this).
However - under the same circumstances - this will fail with the error given in the question
scp.upload!(my_file, "/foo/bar/")
The only solution I've found is to first create the path you want locally, and then upload with the :recursive option on, like so:
scp.upload!("bar/", "/foo" :recursive => true)
where ./bar contains my_file.