I based my Star Trek mod off of Final Frontier. However, the solar systems don't start with any planets. They are all empty. The only changes in the python I made was to change the capital building back to the palace and to change the starting year to 2245. What happened?

No idea, but someone has a tutorial (http://forums.civfanatics.com/showthread.php?t=236028) about modding FF and the planets/systems. It might answer your questions.

Trouble is, I am trying to have the mod work with a random map - not a scenario.

This might be a long shot. But it is supposed that the random map starts empty then on first turn python code randomly fill systems with planets. Now it might be that the starting year/turn is hard-coded in python code. Try looking this up.

The start year is indeed set in the python, though I don't know why. No matter what the start year is, no change.

I have no idea if this is related, but when I exit the game (to main menu or desktop) I get a CTD and windows says the memory could not be "read". Also, I don't get messages that units were damaged in hostile terrain.

EDIT: I tried changing "BUILDINGCLASS_CAPITOL" to "BUILDINGCLASS_PALACE" in the CvSolarSystem file and it fixed the problem but the civs all had the great wall texture around their culture and the city screen was gone. I tried modifying the python further to fix this and the problem returned. I have not been able to fix it since. Changing the XML did not help.

EDIT: After another, more careful/complete cleanup of the file, the problem is solved.

OK, I've fixed the worst bugs (CTD for exit to main menu, no gold entering treasury, no starting planets), but I have a couple bugs left to solve: CTD when exiting to desktop and the fact that I can't build buildings - either naturally or using a GP! The python files are completely clean. This is a nightmare. I with I had a python person working on the mod.

EDIT: I should also mention that the AI can build buildings. It's just the player that can't.