Sachverhalt:
A. Die Y._ AG gewinnen in der Grube "Paradies" Bänderton für die Herstellung von Backsteinen. 1993/1994 erfolgte eine Erweiterungsplanung für den Materialabbau verbunden mit einer Waldrodung.
Am 2. November 2001 wurde der Y._ AG die Errichtung einer Inertstoffdeponie in der Tongrube Paradies bewilligt. Der Betrieb der Deponie wurde der Firma X._ übertragen. Dieser wurde am 25. Juni 2002 die Betriebsbewilligung erteilt, befristet auf den 30. Juni 2007.
B. Am 30. März 2007 erteilte das Amt für Umwelt der Firma X._ die Bewilligung zur Entgegennahme von "anderen kontrollpflichtigen Abfällen und weiteren nicht VeVA-klassierten Abfällen" gemäss der Verordnung vom 22. Juni 2005 über den Verkehr mit Abfällen (VeVA; SR 814.610), die am 1. Januar 2006 in Kraft getreten war. Die Bewilligung wurde - wie die laufende Betriebsbewilligung - bis zum 30. Juni 2007 befristet.
C. Am 26. Juni 2007 verlängerte das Amt für Umwelt die Betriebsbewilligung der Firma X._ sowie die Bewilligung zur Entgegennahme von anderen kontrollpflichtigen Abfällen und weiteren nicht VeVA-klassierten Abfällen.
Gegen diesen Entscheid erhob die Interessengemeinschaft "Sichere Ziegeleistrasse", bestehend aus A._ und weiteren Anwohnern der Ziegeleistrasse, am 27. Juli 2007 Rekurs beim Departement. Sie beantragten, die Betriebsbewilligung sei nicht zu verlängern, weil die Erschliessung der Deponie über die Ziegeleistrasse für die Anwohner unzumutbar sei. Überdies beanstandeten sie, dass die neue Betriebsbewilligung eine Sonderbewilligung für die Ablagerung von Abfällen enthalte, die in einer Inertstoffdeponie nicht vorgesehen sei.
Am 27. November 2007 trat das Departement auf den Rekurs nicht ein.
D. Die dagegen erhobene Beschwerde wies das Thurgauer Verwaltungsgericht am 14. Mai 2008 ab, weil die Vorinstanz die Rekurslegitimation der Beschwerdeführer zu Recht verneint habe.
Gleichentags wies das Verwaltungsgericht eine weitere Beschwerde von A._ und Konsorten ab, die sich gegen den Gestaltungsplan "Materialabbau- und Deponieareal Paradies" richtet. Dieser sieht eine Erweiterung der Deponie durch eine Aufschüttung der Tongrube bis zu 10 m über dem ursprünglichen Terrain vor, um zusätzlich 380'000 m3 Inertstoffmaterial und ca. 80'000 m3 unverschmutzten Aushub ablagern zu können. Dieser Entscheid ist Gegenstand des Urteils 1C_361/2008 vom 27. April 2009.
E. Gegen den verwaltungsgerichtlichen Entscheid i.S. Betriebsbewilligung haben A._ und die weiteren im Rubrum genannten Personen am 22. August 2008 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen die Aufhebung der Entscheide des Verwaltungsgerichts und des Departements und die Rückweisung der Sache zu neuer Beurteilung an das Verwaltungsgericht oder eine seiner Vorinstanzen. Zudem ersuchen sie um Gewährung der aufschiebenden Wirkung.
Die Firma X._ (im Folgenden: Beschwerdegegnerin) und das Amt für Umwelt beantragen Abweisung der Beschwerde, soweit darauf einzutreten sei.
F. Das Bundesamt für Umwelt (BAFU) ist der Auffassung, die Rekurslegitimation der Beschwerdeführer hänge davon ab, ob die notwendigen Massnahmen betreffend Immissionsschutz in den Bereichen Lärmbekämpfung und Luftreinhaltung schon in den vorgelagerten Verfahren (Sondernutzungsplan, Baubewilligung, Errichtungsbewilligung) angeordnet worden seien; wenn ja, seien diese Massnahmen nicht mehr Gegenstand des Betriebsbewilligungsverfahrens. Ob dies der Fall sei, lasse sich den Akten nicht entnehmen. Aus abfallrechtlicher Sicht hält das BAFU die Betriebsbewilligung vom 26. Juni 2007 grundsätzlich für bundesrechtskonform.
Die Parteien und das Amt für Umwelt nahmen zur Vernehmlassung des BAFU Stellung. Die Beschwerdeführer machen geltend, sie könnten die vom BAFU aufgeworfene Frage nicht beantworten, weil ihnen im gesamten Verfahren stets die Akteneinsicht verweigert worden sei.
G. Am 13. Oktober 2008 wies das Bundesgericht das Gesuch der Beschwerdeführer um Gewährung der aufschiebenden Wirkung ab.

Erwägungen:
1. Die Beschwerdeführer, denen im kantonalen Verfahren die Rekursberechtigung abgesprochen wurde, sind legitimiert, dagegen Beschwerde in öffentlich-rechtlichen Angelegenheit zu erheben (<ref-law>). Da auch die übrigen Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde einzutreten.
2. Gemäss § 44 Ziff. 1 des Thurgauer Gesetzes über die Verwaltungsrechtspflege vom 23. Februar 1981 (VRG/TG) ist zum Rekurs berechtigt, wer durch einen Entscheid berührt ist und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat. Die Beschwerdeführer sind der Auffassung, das Verwaltungsgericht habe ihre Rekursberechtigung nach dieser Bestimmung willkürlich verneint und ihnen deshalb das rechtliche Gehör verweigert.
2.1 Gemäss <ref-law> wendet das Bundesgericht das Recht von Amtes wegen an; es prüft jedoch die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist.
Zu dem von Amtes wegen anzuwendenden Bundesrecht gehört auch <ref-law>. Danach muss sich eine Person, die zur Beschwerde an das Bundesgericht berechtigt ist, an allen Verfahren vor allen kantonalen Vorinstanzen als Partei beteiligen können. Die Berechtigung zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ergibt sich aus <ref-law>. Ob dessen Voraussetzungen vorliegen, prüft das Bundesgericht frei.
Der von den Beschwerdeführern erhobenen Rüge der willkürlichen Anwendung von kantonalem Recht käme daher nur dann selbständige Bedeutung zu, wenn das kantonale Recht eine grosszügigere Regelung der Beschwerdelegitimation kennen würde als das Bundesrecht. Das wird von den Beschwerdeführern nicht geltend gemacht.
Im Folgenden ist die Rekursberechtigung der Beschwerdeführer daher am Massstab von <ref-law> zu prüfen.
2.2 Diese Bestimmung verlangt neben der formellen Beschwer (lit. a), dass der Beschwerdeführer über eine spezifische Beziehungsnähe zur Streitsache verfügt (lit. b) und einen praktischen Nutzen aus der Aufhebung oder Änderung des angefochtenen Entscheids zieht (lit. c). Ein schutzwürdiges Interesse liegt vor, wenn die tatsächliche oder rechtliche Situation des Beschwerdeführers durch den Ausgang des Verfahrens beeinflusst werden kann (vgl. Botschaft vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege, BBl 2001 S. 4236). Die Voraussetzungen von Art. 89 Abs. 1 lit. b und c BGG hängen eng zusammen; insgesamt kann insoweit an die Grundsätze, die zur Legitimationspraxis bei der Verwaltungsgerichtsbeschwerde nach Art. 103 lit. a des früheren Organisationsgesetzes vom 16. Dezember 1943 (OG) entwickelt worden sind, angeknüpft werden (<ref-ruling> E. 1.3.1 S. 252 f., 353 E. 3 S. 356 f., 400 E. 2.2 S. 404, je mit Hinweisen).
3. Die Technische Verordnung über Abfälle vom 10. Dezember 1990 (TVA; SR 814.600) unterscheidet zwischen der Errichtungs- und der Betriebsbewilligung für Deponien (Art. 21 Abs. 1 und 2 TVA). Die gleiche Unterscheidung liegt auch dem Thurgauer Gesetz über die Abfallbewirtschaftung (Abfallgesetz; AbfallG) vom 4. Juli 2007 zugrunde (vgl. §§ 8 und 9 AbfallG).
3.1 Gegenstand der Errichtungsbewilligung ist die Erstellung der Deponie, d.h. die Anlage. Im Verfahren der Errichtungsbewilligung wird geprüft, ob ein Bedarf nachgewiesen ist, die Deponie in der Abfallplanung ausgewiesen ist, und ob die für den vorgesehenen Deponietyp geltenden Anforderungen, namentlich an den Standort, erfüllt sind (vgl. Art. 24 und 25 TVA). Die Errichtungsbewilligung legt den Deponietyp fest und enthält allfällige Beschränkungen der darin zugelassenen Abfälle sowie nötigenfalls weitere Auflagen oder Bedingungen zum Schutz der Umwelt (Art. 25 Abs. 2 TVA).
3.2 Im Betriebsbewilligungsverfahren prüft die Behörde dagegen, ob Gewähr besteht, dass die Abfälle vorschriftsgemäss abgelagert werden und der Nachweis über die volle Deckung der Kosten für die Abschlussarbeiten und die erforderliche Nachsorge erbracht ist (Art. 27 Abs. 2 TVA). Hierfür muss der Betreiber in seinem Gesuch u.a. das Betriebsreglement einreichen, das insbesondere die Pflichtenhefte des Deponiepersonals enthält und die Anforderungen der TVA an den Betrieb konkretisiert (Art. 26 Abs. 1 lit. c TVA). Die Betriebsbewilligung legt für den Betreiber verbindlich fest: den Deponietyp, allfällige Einzugsgebiete, allfällige Beschränkungen der nach Anhang 1 zugelassenen Abfälle, Anforderungen an den Nachweis der Zulassung, während des Betriebs und nach Abschluss der Deponie vorzunehmende Kontrollen, Unterhaltsarbeiten und Dokumentation sowie nötigenfalls weitere Auflagen und Bedingungen zum Schutz der Umwelt (Art. 27 Abs. 3 TVA).
3.3 Im Entscheid "Chrüzlen" (1A.128/1993 vom 28. März 1994, publ. in URP 1994 S. 148, E. 5a) hat das Bundesgericht allerdings festgehalten, dass die in der TVA vorgesehene Aufteilung der umweltschutzrechtlichen Deponiebewilligung in eine Errichtungs- und eine Betriebsbewilligung nicht zu einer Beeinträchtigung der Koordination der Bewilligungsverfahren führen darf (vgl. Art. 20 TVA und Art. 25a RPG). Deshalb seien sämtliche Fragen, die für die Erteilung der grundsätzlichen Deponiebewilligung (Errichtungsbewilligung) entscheidend sind, in diesem der Koordinationspflicht unterliegenden Verfahren zu beurteilen. Nur Fragen, die nicht untrennbar mit diesem Grundsatzentscheid zusammenhängen, dürften unter Beachtung der Erfordernisse des Rechtsschutzes in die spätere Phase der Betriebsbewilligung verwiesen werden.
Insofern werden die grundsätzlichen umweltschutzrechtlichen Fragen bereits im Verfahren der Errichtungsbewilligung und der mit dieser koordinierten Bewilligungen entschieden. Sind diese Bewilligungen rechtskräftig geworden, können sie anlässlich der Erteilung der Betriebsbewilligung oder ihrer Verlängerung nicht mehr grundsätzlich in Frage gestellt werden.
3.4 Das bedeutet jedoch nicht, dass die Betriebsbewilligung für die Anwohner völlig bedeutungslos wäre: Werden etwa Einwände gegen die Zuverlässigkeit, Qualifikation oder finanzielle Leistungsfähigkeit des Betreibers und dessen Personal erhoben, so müssen diese Einwände gegen die Betriebsbewilligung geltend gemacht werden. Gleiches gilt, sofern zusätzliche umweltschutzrechtliche Auflagen für den Betrieb der Anlage gefordert werden, die keine Änderung der Anlage bedingen (z.B. Einschränkung der Betriebszeiten oder zusätzliche Sicherheitsauflagen für den Transport auf der Strasse).
4. Fraglich ist allerdings, wie es sich verhält, wenn die Betriebsbewilligung - wie im vorliegenden Fall - nicht erstmals erteilt, sondern verlängert wird.
4.1 Die Beschwerdegegnerin und das Amt für Umwelt weisen darauf hin, dass regelmässig ein Anspruch auf Verlängerung der Betriebsbewilligung besteht, sofern sich die Rahmenbedingungen nicht geändert haben und die regelmässig durchgeführten Kontrollen und Betriebsbegehungen keine Hinweise auf eine nicht vorschriftsgemässe Abfallbewirtschaftung zeigen. Die Betriebsbewilligung sei nur deshalb auf fünf Jahre befristet, um der technologischen und gesetzgeberischen Entwicklung Rechnung zu tragen und um auf allfällige Fehlentwicklungen im Betrieb reagieren zu können (§ 9 Abs. 3 AbfG/TG).
Die Beschwerdelegitimation könne daher nicht von einem Vergleich des Zustands mit und ohne Deponie abhängen; entscheidend sei vielmehr, ob sich im Vergleich zum Betrieb vor der Verlängerung der Bewilligung Änderungen ergeben, welche die Beschwerdeführer besonders berühren. Dies sei nicht der Fall wenn, wie im vorliegenden Fall, alle massgebenden Grenz- und Richtwerte eingehalten werden und der Betreiberin zumutbare ergänzende Auflagen zur Reduktion der Immissionen gemacht worden seien.
Könnte die Betriebsbewilligung alle fünf Jahre grundsätzlich in Frage gestellt werden, hätte dies eine grosse Rechtsunsicherheit zur Folge. Für Erstellung und Betrieb von Abfallanlagen seien grosse Investitionen erforderlich. Damit diese sinnvoll amortisiert werden könnten, müsse der Betrieb auf einen langen Zeitraum hin ausgerichtet sein. Eine Gutheissung der Beschwerde und eine Rückweisung der Sache an die Vorinstanz hätte eine Einstellung des Deponiebetriebs zur Folge, was völlig unangemessen wäre.
4.2 Im Fall der Verlängerung einer befristeten Bewilligung ist die zuständige Behörde nicht stets zur neuerlichen Durchführung des gesamten Bewilligungsverfahrens verpflichtet. Der Sinn der Befristung liegt aber darin, dass am Ende der Frist der Fall neu überprüft werden kann; der Bewilligungsinhaber hat nach Ablauf der Bewilligungsdauer keinen Anspruch auf unveränderte Fortsetzung des Bewilligungsverhältnisses sondern muss, je nach den Umständen, damit rechnen, dass die Bewilligung wegen neuer rechtlicher oder tatsächlicher Verhältnisse angepasst oder sogar nicht mehr verlängert wird (<ref-ruling> E. 1 S. 133). Dies muss von der zuständigen Behörde sorgfältig geprüft werden; eine routinemässige Verlängerung genügt nicht (Entscheid der Umweltschutz- und Energiedirektion des Kantons Appenzell-Innerrhoden vom 1. Oktober 1999, ARGVP 1999 S. 36).
Dritte, die zur Anfechtung der ersten Betriebsbewilligung befugt gewesen wären, müssen deshalb die Möglichkeit haben, geltend zu machen, die tatsächlichen oder rechtlichen Verhältnisse hätten sich derart verändert, dass die Bewilligung verweigert oder angepasst werden müsse, z.B. durch die Verfügung neuer Bedingungen und Auflagen. Dies wird nur in Ausnahmefällen dazu führen, dass der Deponiebetrieb während der Dauer des Rechtsmittelverfahrens eingestellt werden muss; in aller Regel wird es angezeigt sein, der Beschwerde die aufschiebende Wirkung zu entziehen, um die Entsorgungssicherheit nicht zu gefährden; notfalls kann im Wege vorsorglicher Massnahmen die vorläufige Einhaltung gewisser zusätzlicher Massnahmen angeordnet werden.
5. Im vorliegenden Fall ergibt sich Folgendes:
5.1 Der Rekurs richtete sich vor allem gegen die Erschliessung der Deponie über die Ziegeleistrasse.
Diese Frage betrifft die Anlage als solche und wurde bereits im Verfahren der Errichtungsbewilligung sowie des vorangegangenen Gestaltungsplanverfahrens rechtskräftig entschieden. Zwar ist die Erschliessung der Deponie erneut im Zusammenhang mit der projektierten Erweiterung der Deponie zu prüfen. Dies ist aber Gegenstand des Gestaltungsplanverfahrens (vgl. dazu Urteil 1C_361/2008 vom 27. April 2009) und nicht des Betriebsbewilligungsverfahrens. Soweit die Beschwerdeführer eine andere Erschliessung der bestehenden Deponie verlangen, hat das Verwaltungsgericht daher die Rekursberechtigung zu Recht verneint.
5.2 Fraglich ist dagegen, ob die kantonalen Behörden nicht hätten prüfen müssen, ob den Anliegen der Beschwerdeführer durch zusätzliche Auflagen und Bedingungen für den Betrieb Rechnung getragen werden könnte, beispielsweise durch einen weitergehenden Transfer der Anlieferungen auf die Bahn oder durch die Anordnung vorsorglicher Massnahmen für den Lastwagentransport. Dies gilt jedenfalls, soweit sich die Beschwerdeführer auf neue Tatsachen berufen (schlechte Erfahrungen mit der alten Betriebsbewilligung; angeblich aufgetretene Gebäudeschäden, usw.) oder neue rechtliche Gegebenheiten geltend machen (Ausdehnung der Betriebsbewilligung auf zusätzliche Abfallarten, die erhöhte Sicherheitsvorkehrungen erfordern).
Die Auffassung der kantonalen Behörden, zusätzliche umweltschutzrechtliche Auflagen seien in der Betriebsbewilligung generell unzulässig, ist unzutreffend, wie sich bereits aus Art. 27 Abs. 3 lit. f TVA ergibt. Voraussetzung ist lediglich, dass sich diese Auflagen an den Betreiber der Deponie richten und von diesem umgesetzt werden können. So verlangt Ziff. 1.9 der Errichtungsbewilligung für die Inertstoffdeponie Paradies ausdrücklich, dass im Rahmen der Betriebsbewilligung ein Konzept eingereicht wird, wie den umweltrechtlichen Anliegen der Anlieferung per Bahn/Strasse Rechnung getragen werden kann. Dieses Konzept ist also Teil der Betriebsbewilligung, weshalb zusätzliche Auflagen und Bedingungen zu diesem Punkt in die Betriebsbewilligung gehören. Das Amt für Umwelt hat denn auch in den Ziff. 18 ff. der Betriebsbewilligung vom 26. Juni 2007 zusätzliche Auflagen zum vorsorglichen Immissionsschutz erlassen. Ob diese ausreichen oder nicht, ist keine Frage der Legitimation, sondern der materiellen Beurteilung. Auch in diesem Punkt ist daher die Rekursberechtigung der Beschwerdeführer zu bejahen.
5.3 Schliesslich haben die Beschwerdeführer auch gegen die Verlängerung der Bewilligung zur Entgegennahme von anderen kontrollpflichtigen Abfällen und weiteren nicht VeVA-klassierten Abfällen rekurriert, mit der Begründung, damit werde die Ablagerung von Sonderabfällen bewilligt, die in Inertstoffdeponien nicht vorgesehen seien.
5.3.1 Zwar war diese Bewilligung schon zuvor, am 30. März 2007, befristet bis zum 30. Juni 2007, erteilt worden. Die erste Bewilligung wurde jedoch (soweit aus den Akten ersichtlich) den Beschwerdeführern weder zugestellt noch publiziert. Insofern muss den Beschwerdeführern Gelegenheit gegeben werden, diese Bewilligung anlässlich ihrer Verlängerung anzufechten. Da die Abfälle an ihren Häusern vorbei transportiert und in ihrer unmittelbaren Nähe abgelagert werden, haben sie hieran ein schutzwürdiges Interesse.
5.3.2 In diesem Punkt besteht auch kein Vorrang des hängigen Verfahrens betreffend Gestaltungsplan und Baugesuch: Das parallele Verfahren betrifft die Frage der Erweiterung der Deponie durch zusätzliche Ablagerungen über die frühere Terrainhöhe hinaus. Im vorliegenden Fall ist dagegen streitig, welche Abfallarten vom Betreiber im Rahmen der bestehenden Bewilligungen abgelagert werden dürfen. Diese Frage stellt sich auch dann, wenn das Erweiterungsvorhaben aus irgend einem Grund scheitern sollte. Auch in diesem Punkt ist daher die Beschwerdebefugnis der Beschwerdeführer zu bejahen.
5.3.3 Zwar gibt es keinen Grund, an der Aussage des Amts für Umwelt zu zweifeln, wonach die fraglichen Stoffe von Anfang an in der Deponie abgelagert worden sind und nur aufgrund des Inkrafttretens der VeVA eine gesonderte Bewilligung erforderlich wurde. Auch das BAFU hält die Beschwerde in diesem Punkt für unbegründet. Streitgegenstand des vorliegenden Verfahrens ist jedoch nur die Eintretensfrage. Insofern ist es dem Bundesgericht verwehrt, anstelle der kantonalen Instanzen einen materiellen Entscheid zu fällen.
6. Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen, der angefochtene Entscheid insofern aufzuheben und die Sache zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen, soweit den Beschwerdeführern die Rekursberechtigung gegen die Bewilligung zur Entgegennahme von anderen kontrollpflichtigen Abfällen und weiteren nicht VeVA-klassierten Abfällen verweigert wurde. Zu bejahen ist die Legitimation der Beschwerdeführer ferner, soweit sie zusätzliche Auflagen in der Betriebsbewilligung zum Schutz vor Lärm- und Luftimmissionen des Deponiebetriebs verlangen. Im Übrigen ist die Beschwerde abzuweisen.
Bei diesem Ausgang des Verfahrens rechtfertigt es sich, die Gerichtskosten den Beschwerdeführern und der Beschwerdegegnerin je zur Hälfte aufzuerlegen und die Parteikosten wettzuschlagen (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Thurgau vom 14. Mai 2008 betreffend Betriebsbewilligung Inertstoffdeponie Paradies wird insoweit aufgehoben und zu neuer Beurteilung an das Verwaltungsgericht zurückgewiesen, als den Beschwerdeführern die Rekursberechtigung gegen die Verlängerung der Bewilligung zur Entgegennahme von anderen kontrollpflichtigen Abfällen und weiteren nicht VeVA-klassierten Abfällen abgesprochen und die Überprüfung der Auflagen der Betriebsbewilligung zum Schutz der Anwohner vor Lärm- und Luftimmissionen abgelehnt wurde. Im Übrigen wird die Beschwerde abgewiesen.
2. Die Sache wird zur Neuverlegung der Kosten des vorangegangenen Verfahrens an das Verwaltungsgericht zurückgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern und der Beschwerdegegnerin je zur Hälfte auferlegt.
4. Es werden keine Parteientschädigungen zugesprochen.
5. Dieses Urteil wird den Parteien, dem Amt für Umwelt, dem Departement für Bau und Umwelt und dem Verwaltungsgericht des Kantons Thurgau sowie dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 27. April 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber