I'm kind of going off a hazy memory but I believe my co-worker was having a smiliar problem and i traced it down to the fact that her enterprise manager on her work PC was at a different service pack then the SQL servers. She was unable to run packages as jobs in some fashion. Are you using SQL Server 7.0 or 2000? Definitely check your versions to make sure you are at the same service packs if you are using 7.