IO540 yes i do mean that you cannot cut and paste 
beacuse AIS does not accept GPS co-ords in that format they want DDMMNDDDMME etc.
You have lost me now
Where are these coordinates coming from? Are you creating user waypoints, and thus ending up with lat/long coordinates in your ICAO flight plan?
If so, may I make a radical suggestion: plan your flights as if you did them IFR, i.e. use waypoints which are VORs, NDBs, airway intersections (e.g. ALKIN) etc. Most of my UK flying is VFR and I almost never have to invent a waypoint. Planning for radio navigation has many navigational advantages but if I say any more somebody will jump on me... but, reading the next bit of your post you obviously know all this, so I am even more puzzled.
Also the problem with the flight change is that the program forgets to output the actual waypoint! 
That sounds like a bug. Flitestar has a fair few of those.
Navbox has a bug in that if you use an airfield ident (e.g. EGKB) as a waypoint (which is not legal on a flight plan) it quietly drops it when it generates the flight plan. I have told them about this years ago; the reply was that you should not be doing it in the first place
I was hoping this is a current bug - have you had experience of using the ICAO flight plan for VFR?
I have never used the Flitestar flight plan as it is. I use FS as a route drawing tool and a plog generator, and mainly for IFR. One could use the built-in flight plan generator; print to say Winfax and fax the FP straight to the airport of departure, etc. But I file flight plans using homebriefing.com and one just enters the route. The aircraft data tends to be predefined for the user profile.
If you are ending up with lat/long coordinates then I can understand why you don't want to do this...
Does the navbox do this better? (I prefer the RNAV co-ords since AIS accept these and are quick to enter into my GPS and backup VOR nav systems can also be used )
I've never used Navbox to generate RNAV data, but yes a VOR reference is another way for you to file a VFR FP with a random waypoint on it.
Having done about 16 hours of european planning with flighstar, whilst superficially very nice, I have many frustrations - I have decided to buy navbox anyway and have ordered it online!
PS. Can navbox be given a notam co-ordinate and radius/bounding box to see where the NOTAM is and then print it? or do people no of a a NotamPlot for Europe?
No idea - I always copy/paste the route into ais.org.uk.
As I mention, try to use airways intersections where there isn't a handy navaid. That avoids all the problems which I think you are finding.
Plus ATC gives you less hassle if you use intersections; it tells them you are navigating with a (half decent) GPS so they are much less likely to have problem with you than a 100%-VFR pilot navigating from one village to the next. VFR flight abroad is generally easier than in the UK; you get long clearances through Class C/D at FL065 etc but you need to sound like you know what you are doing.