Many questions about the integers are recursively enumerable (like: what are the counterexamples to Fermat's last theorem?), but this doesn't really reveal anything about any deeper structure. Part of the conjecture is, indeed, that the set of numbers that are a sum of three cubes is recursive, which is given by a simple condition on the residue modulo 9 (see a sibling comment). However, mathematicians don't usually think about recursiveness of sets when they think about whether a problem has been "solved." It's more about whether some structure has been satisfyingly illuminated (maybe, to make something completely up, triples of numbers whose cubes sum to a particular number are found to be in one-to-one correspondence with "tripolar Hopfian unital schemes," and if something is known about them this might be satisfying). Of course, knowing whether or not a set has a recursive description is nice, too.

Here's something I've wondered about. In knot theory, a "knot" is a closed loop of string in 3d space, and if you allow the string to pass through itself it can obviously be unknotted (put into a form where it is a closed loop flat on a table). An unknotting is a sequence of pass-throughs to unknot it, and the unknotting number is the minimal number of pass-throughs among all unknottings. Unknotting sequences are actually recursively enumerable, but it's unknown whether there is a finite-time algorithm to compute unknotting number!