The dummy variable trap is concerned with cases where a set of dummy variables is so highly collinear with each other that OLS cannot identify the parameters of the model. That happens mainly if you include all dummies from a certain variable, e.g. you have 3 dummies for education "no degree", "high school", and "college". If you include all dummies in the regression together with an intercept (a vector of ones), then this set of dummies will be linearly dependent with the intercept and OLS cannot solve. For this reason dummies are automatically dropped by most statistical packages.
For question 1, having a part-time and a temporary work dummy should not have this problem because they are not mutually exclusive and exhaustive. For instance, people can work full-time but on a temporary basis. However, if in your sample (for whatever reason) all part-time employees are also temporary workers then again one of your dummies will be dropped. As a side note: the bigger problem with such a regression is an endogeneity problem due to self-selection, e.g. why are some individuals temporary workers? Depending on the reason and its relation to the outcome this may bias the results.
Regarding question 2, changing the baseline dummy is a matter of interpretation. Which baseline you choose depends on what you want to answer. If you want to see how much college graduates earn more than high-school graduates then choosing high-school graduates as the baseline makes sense. Then the coefficient of the graduate dummy can be interpreted as the difference in the outcome between college and high-school graduates.