Getting a 401 only on select REST calls (token auth)

I am probably doing something stupid, but I keep getting 401s when making REST calls to our v13 BIG-IP devices. What is weird is that the same exact token works fine when sending GETs, but POSTs/PUTs/PATCHes throw a 401. I am using the built-in admin account and all REST calls work fine when using basic auth.

I am doing every step outlined in this document: https://devcentral.f5.com/articles/demystifying-icontrol-rest-part-6-token-based-authentication, so my calls (in C) look like this:

1. Send JSON object with username/password/loginProviderName to /mgmt/shared/authn/login
2. Retrieve the token from the response (always a 26-character string)
3. POST to any endpoint (node, pool, virtual server, etc.) with the X-F5-Auth-Token header equaling the 26-character token value
4. This will always return a 401

Just seems odd that if I leave the token header in there and just add an Authorization header for basic auth, the request works just fine.

Any ideas?