How to properly trigger build from the REST API in teamcity with a specific vcs number?

I am working on a C# tool to trigger build with the REST API of TeamCity. I want to trigger build with specific vcs number, so here's what I'm doing:

POST => teamcity-server/httpAuth/app/rest/buildQueue 
HEADER => basicAuthCredentials
BODY => 

<build>
    <buildType id="SomeValidBuildId"/>
    <properties>
        <property name="SAMPLE_TEST" value="VERY_TESTY"/>
    </properties>
    <lastChanges>
        <change locator="version:4354174,buildType:(id:SomeValidBuildId)" />
    </lastChanges>
</build>

The request is working, the build has my properties and my specified vcs number. Everything is fine, except when there was no previous build associated to that vcs number, the request fails and show this error message:

Http request failed: 
error : Responding with error, status code: 404 (Not Found).
error : Details: jetbrains.buildServer.server.rest.errors.NotFoundException: Nothing is 
found by locator 'version:4354174,buildType:(id:SomeValidBuildId),count:1'.
error : Could not find the entity requested. Check the reference is correct and the user has permissions to access the entity.

The build has access to VcsRoot settings, and everything it needs, how do can I trigger custom build on vcs number that were never built before?

Solution

This was against vcs perforce, running curl from windows cmd line, and allows me to trigger TeamCity builds on a given p4 branch and change list

curl -u "teamcityUser:teamcityPassword" -X POST -d "{
""buildType"": {""id"": ""teamcityProjectId""},
""branchName"":""//p4/branch"",
""revisions"": {""revision"":[{
""version"":""59933"",
""vcsBranchName"":""//p4/branch""
}]}
}" --header "Content-Type: application/json" -H "Accept: application/json" <TeamCity Server host>:<port>/httpAuth/app/rest/buildQueue