This actually sounds like a fuel pump problem but the way I would start with something like this is to check first the spark plug wires to see if you are getting spark in all cylinders then Turn the ignition but do not cranck you should hear a bit of a whinning noise when you do that and that is usually an indication of the fuel pump working if you do not here this noise then assume fuel pump is burnt out right away. I would also take out a sspark plug and check for some residue buildup this usually occyrs when the there is flooding of the fuel system that will tell you that the pump is sending out fuel. No an oil change or tranny fluid may not have caused this however how stiff is the shifter? By the way when you did tranny service what type of fluid did you use?
