If you go with the "auto-deceleration if over top-speed"-idea this will have limited impact, but as you said be a nice touch. And maybe set a precedence for future new kinds of nebulas and environmental hazards (which might have much more impact) 
...thinking about it, you could even say that phase ships are invisible while cloaked within a nebula, at least it would mitigate some of the inherent problems...ah, well.
This idea would certainly make playing phase ships more interesting than cloak, de-cloak, unload, re-cloak, wash, rinse and repeat.
Or perhaps they don't show up on long range scanners such as the tactical map and "R" targeting when in a nebula (unless they are yours of course).
Well, invisibility might be a bit much (particularly as it's been discarded previously) but nebulae giving increased or reduced cloak cost when inside would make them interesting. Possibly increased would work better, so if you were being harassed by phase cloak ships as a bigger ship you'd have an interesting tradeoff- stick it out, or enter the nearest nebula and lose speed but be safe from cloaked attacks?
That would also conceptually work with the extra cost when flying through another vessel- a nebula's not really as solid as a ship, but it's extra stuff to move through so cloaking costs more.
But then having nebulae reduce cloak cost would also be interesting, and would be a more positive mechanic (encouraging you to do something rather than discouraging you from doing something).
