Fix your Timestep does not deal with graphical stuttering even in a correct implementation. Assume a working implementation where the only game logic is physics. If physics is at 50Hz, and render can run at 200Hz, you're only going to see 50Hz unless you implement visual interpolation. Likewise, if your framerate varies, expect stuttering.
The rest of this answer is largely a re-explanation of the above, with some extra points.
Possibility 1: Cost too high - missing updates
If you're often missing frames per se, i.e. not even getting a single frame in a given update then your per-frame logic is too costly and you need to reduce it, e.g. have fewer physics bodies active.
Possibility 2: Cost reasonably low against a fluctuating frame period
I'm getting caught quite often in the while loop, i.e. it runs my logic more than once
Therein lies your problem. When the system is running your code on true fixed-rate vsync, you expect the same number of logic updates per display update. 1 or 10, but it should always be same - if it is, no stuttering. Android frame rate is quite steady, on my devices it's just under 60fps for a light NDK/OpenGL app, but it does fluctuate. Read on.
There's quite a difference in expectations between setups where you
- have direct control over the core (while) loop, which you can run at the highest rate possible given the ops coded there in C/C++ code, and where if you take too long to process / render, that is entirely your own concern - but typically you have many render frames per logic frame;
- have a (relatively) fixed frame rate dictated to you by the system, which calls your update (
onDrawFrame() in this case) as a callback e.g. browser JS, Flash, or in this case, Android - here you have one or more logic frames per render frame (see the inversion from the above case?), and you absolutely must complete at least one logic update per frame period (dictated by the system) for things to proceed sanely - this which is fundamentally different.
From early experiences with this, I believe Gaffer's concept (in that article) is geared to the former, i.e. primarily AAA desktop and console games written in C++ where the core loop runs as fast as possible and often without any external timing mechanism (ever seen those Quake demos where they're getting like 400fps?). Let's look at some examples to see what can happen with the latter.
Example A - the display frequency is relatively steady, around 16.7ms period, give or take a millsecond or 2, and for maybe 90% of frames, it is spot on at 16.7. Let's say your logic takes 9ms. Most frames, then, you'll manage just one update. But due to unforeseen delays in the Android operating system, the period on which
onDrawFrame() fluctuates and sometimes jumps up to 18+ ms every so often, say 5% of the time, and then you are going to end up doing 2 logic updates because you have enough time do so instead of just 1...but the actual display frequency hasn't changed so much that it would have been apparent using a one-logic-update-per-display-update approach anyway, so what do you see? Stuttering, of course.
Example B - Your logic processing takes about 16.3ms on average. If at any stage it jumps up by say 0.5ms, and exceeds the point by which the OS intends to render, you'll also see stuttering, the severity of which depends on the frequency with which you exceed that soft limit of around 16.7ms.
Crucially, It's not that the accumulator approach isn't a good one - it's excellent, in fact, and is really the only sane way to handle the fixed timestep required for stable physics without frequent network desync (after all, you cannot just drop the accumulated time, and every client is going to accumulate differently). But if you don't have direct control over the timing loop, you can easily run into problems you didn't expect. And you must appreciate that when the accumulator does build up enough time to run more than one update at a time (the exception rather than the rule), then it may well lead to a jarring visual result. So you will need to do graphical interpolation.
You need interpolation if you want to accurately reflect your maximum frame rate as against your slower logic update rate, and with naive interpolation you may still perceive unwanted variances in frame rate due to occasional double-runs of physics and game logic. Admittedly I'm not an expert on interpolation / extrapolation algorithms but it stands to reason that the more frames you use to calculate averages over, the smoother it's going to look, though too many frames has drawbacks.
When there is a mechanism in place dictating your timing, it's best to just stick with that and not try to work around it - such loops (as opposed to what Gaffer describes) are intended for one update per frame. If there are good solutions for this type of scenario, I'd love to hear them.
However... I've not used Android's Java interface for game dev (only NDK), but what I would suggest (if possible?) is to run a while loop that has nothing to do with
onDrawFrame() but rather just sits in main doing its game / physics logic things, while
onDrawFrame() purely handles rendering at the appropriate time. I don't know how that will sync up or even if it will work at all.
For Android NDK as with most native development, you have direct control over the while loop off which everything runs - game logic and render calls - so the problem there is already solved.