You've almost got it, just a little bit off.
Each User has a set of Devices. This means that when you invoke [aUser valueForKeyPath:@"devices.category"], it's going to give you a collection of the aggregation of the devices' categories.
In other words, if your user has 2 devices, and they (respectively) have a category of "mobile" and "desktop", then "devices.category" will return (mobile, desktop). This is a vector value. It contains multiple elements.
However, you're comparing this to a scalar value (a single element), @"mobile".
What I think you're going for is wanting to select all users that have at least one device that's in the "mobile" category, correct? If that's the case, then you just need to use the ANY keyword, and make your predicate thusly:
[NSPredicate predicateWithFormat:@"ANY devices.category = %@", @"mobile"]
For more information on these aggregate functions, check out the Predicate Programming Guide.