The goal of this clinical research study is to find the highest tolerable dose of Tarceva (erlotinib hydrochloride) that can safely be given in combination with Velcade (bortezomib). The safety of this drug combination will also be studied.

The Study Drugs:

Erlotinib hydrochloride and bortezomib are both designed to block proteins that are thought to cause cancer cells to grow. These drugs may help slow the growth of tumors.

Study Drug Dose Level:

If you are found to be eligible to take part in this study, you will be assigned to a dose level of erlotinib hydrochloride and bortezomib based on when you join the study. Up to 4 dose levels of this study drug combination will be tested. There will be 3-6 participants enrolled at each dose level of the study drug combination.

The first group of participants will receive the lowest dose level of erlotinib hydrochloride (Group 1). If all of Group 1 tolerate that dose level, the next group (Group 2) will receive a higher dose. Each new group will receive a higher dose than the group before it, if no intolerable side effects were seen (Groups 2-4). This will continue until the highest tolerable dose of the study drug combination is found. However, if Group 1 did not tolerate the first dose level, the next group will receive a lower dose (called Dose Level -1). If that dose level is still intolerable, the third group will receive an even lower dose (called Dose Level -2).

The dose of bortezomib will be based in which group you in. Groups 1 and 2 will receive the same dose, Group 3 will receive a higher dose, and Group 4 will receive an even higher dose.

After the highest tolerable dose is found, up to an additional 10 participants, called the "expansion group," will receive the study drug combination at that dose.

Study Drug Administration:

Erlotinib hydrochloride will be taken by mouth 1 time every day for 21-days, called a study "cycle." You should take erlotinib hydrochloride on an empty stomach either 1 hour before eating or 2 hours after eating.

Depending on which dose level you are assigned to, you will receive bortezomib by vein over about 1-5 minutes on Days 1 and 8, or on Days 1, 4, 8, and 11 of each 21-day cycle.

Study Visits:

You will have a single study visit just before each cycle. At these visits, the following tests and procedures will be performed:

• Your performance status will be recorded.
• You will be asked to list any drugs you may be taking, including over-the-counter drugs.
• You will be asked about any symptoms you may have.
• You will have a physical exam, including measurement of your vital signs.
• Blood (about 2 teaspoons) will be collected for routine tests.
• Blood (about 2 teaspoons) will be collected for pharmacodynamic (PD) testing. PD testing is used to look at how the level of study drug in your body may affect the disease.

After every 2 cycles (Cycles 2, 4, 6, and so on), you will have a CT or MRI scan to check the status of the disease.

Length of Study:

You may continue taking the study drugs for as long as you are benefitting. You will be taken off study if the disease gets worse or intolerable side effects occur.

Follow-up Visit:

About 30 days after the last dose of study drugs, you will have a follow-up visit. You will be asked to return any unused study drug. At this visit, the following tests and procedures will be performed:

• Your performance status will be recorded.
• You will be asked to list any drugs you may be taking, including over-the-counter drugs.
• You will be asked about any symptoms you may have.
• You will have a physical exam, including measurement of your vital signs.
• Blood (about 2 teaspoons) and urine will be collected for routine tests.

This is an investigational study. Bortezomib and erlotinib hydrochloride are both FDA approved and commercially available. Bortezomib is FDA approved for the treatment of multiple myeloma. Erlotinib hydrochloride is FDA approved for the treatment of lung cancer and pancreatic cancer. The use of these drugs together is investigational and authorized for use in research only.

Up to 48 participants will take part in this study. All will be enrolled at M. D. Anderson.

Inclusion Criteria:

1. Patients with pathologically confirmed advanced or metastatic cancer that is refractory to standard therapy, relapsed after standard therapy, or who have had no standard therapy that induces a CR rate of at least 10% or improves survival by at least three months.
2. Measurable or non-measurable disease.
3. Patients must be >/= 6 wks beyond treatment with a nitrosourea or mitomycin-C, >/= 4 wks beyond other chemotherapy or external beam radiation therapy (XRT), and must have recovered to </= Grade 1 toxicity for any treatment-limiting toxicity resulting from prior therapy. (Exception: patients may have received palliative low dose XRT one week before treatment provided it is not given to the only targeted lesions).
4. (continued from above) Also, patients who have received non-chemotherapeutic biological agents will need to wait at least 5 half-lives or 4 wks, whichever is shorter, from the last day of treatment.
5. Eastern Cooperative Oncology Group (ECOG) performance status </= 2 (Karnofsky >/= 60%)
6. Patients must have normal organ and marrow function defined as: absolute neutrophil count >/=1,000/mL; platelets >/=50,000/mL; creatinine </= 2 X upper limit of normal (ULN); total bilirubin </= 2.0; ALT(SGPT) </= 3 X ULN; Exception for patients with liver metastasis: total bilirubin </= 3 x ULN; ALT(SGPT) </= 5 X ULN.
7. Women of childbearing potential and men must agree to use adequate contraception (hormonal or barrier method of birth control; abstinence) prior to study entry, for the duration of study participation, and for 30 days after the last dose.
8. Ability to understand and the willingness to sign a written informed consent document
9. For the MTD expansion cohort, patients will be eligible if they meet one of the following criteria: (I) Have an EGFR-sensitive mutation and have been previously treated with EGFR inhibitor therapy but have subsequently developed resistance, OR (II) Have an EGFR-resistant mutation, OR (III) Do not have an EGFR mutation, but have benefited from EGFR inhibitor therapy (including either >/=4 months of stable disease [SD] OR a >/= partial response [PR]).

Exclusion Criteria:

1. Patients with uncontrolled concurrent illness, including but not limited to: ongoing or active infection; altered mental status or psychiatric illness/social situations that would limit compliance with study requirements and/or obscure study results.
2. Uncontrolled systemic vascular hypertension (systolic blood pressure > 140 mm Hg, diastolic blood pressure > 90 mm Hg on medication).
3. Patients with clinically significant cardiovascular disease: history of cardiovascular accident (CVA) within 6 months, myocardial infarction or unstable angina within 6 months, or unstable angina pectoris.
4. Patients with colorectal carcinoma with tumors that demonstrate a Kirsten rat sarcoma (KRAS) mutation.
5. Pregnant or lactating women.
6. Patients with a history of bone marrow transplant within the previous two years.
7. Patients with a known hypersensitivity to any of the components of the drug products.
8. Patients unable to swallow oral medications or with pre-existing gastrointestinal disorders that might interfere with proper absorption of oral drugs.
9. Patients with major surgery within 30 days prior to entering the study.