Patience! I'm not always on here... ;)
Answers in bold.
1- Just got the Bayleaf on Colosseum. Do I have to restart to get the water and fire alternatives, or will i get them later in the game?
You get the other two starters after you beat the main storyline.
2- Can i trade them over to my GBA cartridge straight away, or should I wait until they have fully evolved? (i.e, will I miss out on anything if I trade them now?)
Well, first you have to purify them before you can trade (make them normal - can't trade Shadow Pokemon). You can trade anytime you like after that - BUT only after you've beaten the main storyline. Impossible to trade before then.
3- If I do have to restart (see question 1), are there any other Pokemon that I should get before restarting (like with the legendary dogs on the GBA titles, you can only have 1, so it's worth waiting until these have been caught before restarting).
No need to restart - you get infinite chances to get every Shadow Pokemon eventually, I believe. :)
4- Can I use my save game from colosseum for XD? or do I need 48 seperate blocks for it?
Can't use the same save file for both games, as the games are different. Another 48 blocks I'm afraid.
Hope I helped. And remember that forums tend to get a bit slow now and then.