Sachverhalt:
A. Am 27. August 2004 reichten R._, S._, T._ und U._ (nachfolgend: Beschwerdegegner) beim Gemeinderichteramt A._ gegen X._, Z._ und Y._ (nachfolgend: Beschwerdeführer) eine Eigentumsfreiheitsklage u.a. mit dem Begehren ein, die Beschwerdegegner seien zu verpflichten, die entlang dem Autoabstellplatz A (Parzelle StWE-Nr. 1) in A._ angebrachte Gitterabschrankung zu entfernen, und es sei ihnen richterlich zu verbieten, die allen Miteigentümern zur Nutzung offenstehende Fläche der Garagenhalle (Einfahrt, Zufahrt zu den Plätzen) ausschliesslich zu nutzen (beziehungsweise durch Mieter nutzen zu lassen) und dadurch die Mitnutzung der übrigen Miteigentümer zu verunmöglichen.
Am 7. November 2007 fällte das Gemeinderichteramt folgendes Urteil:
"1. Die Beklagten werden verpflichtet, den Gitterzaun entlang der Front des Autoabstellplatzes A (StWE-Anteil Nr. 1) in A._ auf ihre Kosten zu entfernen.
2. Die Abschrankung zwischen dem Parkplatz A und B, wie er bisher bestand, kann bestehen bleiben.
3. Den Beklagten wird verboten, den Autoabstellplatz als Depotwarenlager zu benutzen, bevor die notwendige Zustimmung der Mehrheit der Miteigentümer vorliegt..."
B. Dagegen reichten die Beschwerdeführer - mit Ausnahme von Z._ - beim Bezirksgericht Brig, Östlich-Raron und Goms, Nichtigkeitsklage ein, welche mit Urteil vom 29. April 2008 abgewiesen wurde, soweit darauf einzutreten war.
C. Die Beschwerdeführer haben die Sache mit Beschwerde vom 28. Mai 2008 an das Bundesgericht weitergezogen. Sie beantragen, das Urteil des Bezirksgerichts Brig sei aufzuheben, und es sei festzustellen, dass die bestehende Abschrankung so bestehen bleiben dürfe, wie sie jetzt bestehe.
Vernehmlassungen wurden nicht eingeholt.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid in Zivilsachen, welcher einen Endentscheid darstellt (Art. 72 Abs. 1, Art. 75 Abs. 1 und Art. 90 BGG). Beim Streit um die Beeinträchtigung des Eigentums von Miteigentümern handelt es sich um eine vermögensrechtliche Angelegenheit, welche der Beschwerde in Zivilsachen unterliegt, wenn der Streitwert wenigstens Fr. 30'000.-- beträgt (<ref-law>). Der Streitwert beträgt unbestrittenermassen Fr. 4'500.--, so dass die Beschwerde in Zivilsachen unzulässig ist.
1.2 Die Beschwerdeführer sind indes der Meinung, es stelle sich eine Rechtsfrage von grundsätzlicher Bedeutung nach <ref-law> (dazu: <ref-ruling> E. 1.2 mit Hinweisen). Sie bestreiten in der Beschwerde in Zivilsachen die Aktivlegitimation der Beschwerdegegner mit der Begründung, es müssten sämtliche Miteigentümer des Stockwerkeigentümeranteils auf der Klägerseite stehen. Es sei erstellt, dass lediglich 4 von 18 Miteigentümern des STWE-Anteils Nr. 1 in A._ Klage eingereicht hätten.
In der Klageantwort hatten die Beschwerdeführer die Aktivlegitimation der Klägerschaft bestritten (pag. S. 125), der Gemeinderichter hat sie jedoch bejaht (pag. S. 309). Da das Bezirksgericht (als Rechtsmittelinstanz) die Rechtsanwendung nur auf Willkür überprüft (Art. 229 Abs. 2 lit. b und c ZPO/VS), ist es auf die Rüge der willkürlichen Bejahung der Aktivlegitimation mangels Substantiierung nicht eingetreten. Die Beschwerdeführer rügen vorweg mit Beschwerde in Zivilsachen eine Verletzung von Bundes(gesetzes)recht und erblicken in der (von der ersten Instanz bejahten) Frage der Aktivlegitimation eine frei zu prüfende Rechtsfrage von grundsätzlicher Bedeutung, welche die Beschwerde zulasse.
Nach der für die staatsrechtliche Beschwerde geltenden Rechtsprechung konnte der Entscheid einer unteren Instanz mitangefochten werden, wenn entweder der letzten kantonalen Instanz nicht sämtliche vor Bundesgericht erhobene Rügen unterbreitet werden konnten, oder wenn solche Rügen zwar von der letzten kantonalen Instanz zu beurteilen waren, jedoch mit einer engeren Prüfungsbefugnis, als sie dem Bundesgericht zusteht (sog. Dorénaz-Praxis, vgl. <ref-ruling> E. 3a S. 311). Im vorliegenden Fall, wo die kantonale Rechtsmittelinstanz nicht die Verletzung des Bundes(gesetzes)rechts, sondern nur des Willkürverbots prüft, bedeutet das, dass der Beschwerdeführer, wenn er unter Berufung auf die Ausnahmeklausel von <ref-law> freie Überprüfung von Bundes(gesetzes)rechts durch das Bundesgericht und damit die Beschwerde in Zivilsachen beansprucht, den erstinstanzlichen Entscheid mitanfechten kann, aber auch muss (dazu: <ref-ruling> E. 2 S. 144, mit Hinweisen zur Entwicklung der Dorénaz-Praxis). Die Beschwerdeführer haben dies unterlassen. Weder aus dem Antrag noch aus der Begründung ergibt sich die Anfechtung des erstinstanzlichen Entscheides bzw. eine Auseinandersetzung mit dessen Erwägungen. Schon aus diesem Grund ist eine freie Prüfung der Rechtsfrage bzw. die Anrufung von <ref-law> ausgeschlossen, die Beschwerde in Zivilsachen unzulässig und darauf nicht einzutreten.
2. 2.1 Damit sind im Folgenden die Ausführungen der Beschwerdeführer zur subsidiären Verfassungsbeschwerde zu prüfen. Sie werfen dem Bezirksgericht in verschiedener Hinsicht willkürliche Tatsachenfeststellungen vor. Gemäss <ref-law> kann mit der Verfassungsbeschwerde die Verletzung von verfassungsmässigen Rechten gerügt werden. Nach Art. 118 Abs. 2 in Verbindung mit <ref-law> kommt eine Berichtigung oder Ergänzung der Sachverhaltsfeststellungen nur dann in Frage, wenn die kantonale Instanz verfassungsmässige Rechte verletzt hat. Wird Letzteres geltend gemacht, ist neben der Erheblichkeit der gerügten Tatsachenfeststellung für den Ausgang des Verfahrens klar und detailliert darzutun, inwiefern diese verfassungswidrig, insbesondere willkürlich (<ref-law>), offensichtlich unhaltbar sein soll, d.h. mit der tatsächlichen Situation in klarem Widerspruch stehe, auf einem offenkundigen Versehen beruhe oder sich sachlich in keiner Weise rechtfertigen lasse (<ref-ruling> E. 7.1 S. 398, mit Hinweisen). Dabei genügt es aber nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift im Einzelnen darzulegen, inwiefern diese willkürlich bzw. unter Verletzung einer verfahrensrechtlichen Verfassungsvorschrift zustande gekommen sein sollen (<ref-ruling> E. 1.4.3 S. 255). Eine materielle Rechtsverweigerung ist nicht schon dann gegeben, wenn eine andere Lösung ebenfalls vertretbar oder gar zutreffender erschiene, sondern nur dann, wenn das Ergebnis schlechterdings mit vernünftigen Gründen nicht zu vertreten ist (<ref-ruling> E. 2a mit Hinweisen; <ref-ruling> E. 3a S. 373).
2.2 Die Vorinstanz hat befunden, der Vize-Gemeinderichter sei in seinem Entscheid zu Recht zum Schluss gekommen, dass die Erstellung eines Gitterzauns nicht als blosse Verwaltungshandlung angesehen werden könne. Bei baulichen Massnahmen, wie sie vorliegend vorgenommen worden seien, gelangten <ref-law> zur Anwendung. Danach bedürften selbst notwendige bauliche Massnahmen, zu denen die Umzäunung eines Abstellplatzes in einer Garagenhalle im Übrigen nicht gehöre, der Zustimmung der Mehrheit aller Miteigentümer. Weil die Zustimmung der Miteigentümer vorliegend nicht eingeholt worden und von diesen auch nachträglich keine Billigung erfolgt sei, seien diese baulichen Massnahmen zu Unrecht erfolgt. Dagegen habe die Abschrankung zwischen den Parkplätzen A und B (der Beschwerdeführer) bereits bei Bezugsbereitschaft im Jahre 1982 bestanden, sodass diese (zugunsten der Beschwerdeführer) nicht beseitigt werden müsse. Zu den übrigen Garagenboxen hätten die Beschwerdeführer keine Ausführungen gemacht. Im Übrigen sei darauf hinzuweisen, dass fünf weitere Garagenboxen bereits kurz nach dem Rohbau des Hauses rechtmässig als Garagenboxen bzw. mit Gitter-Abschrankungen errichtet worden seien. Dies ergebe sich aus den Notizen der Verwaltung und sei von M._, N._, U._ und O._ anlässlich ihrer Einvernahmen bestätigt worden. Diese Garagenboxen seien alsdann auch an der zweiten oder dritten Stockwerkeigentümerversammlung zusätzlich besprochen und genehmigt worden. Das Gegenteil sei von den Beschwerdeführern denn auch nie behauptet worden.
Wenn die Beschwerdeführer geltend machen, es bestünden in der Tiefgarage noch andere eingezäunte Boxen, dann stimmen sie mit dem angefochtenen Entscheid überein. Wenn sie schlicht behaupten, es fehle die Zustimmung der Miteigentümer zu diesen baulichen Massnahmen, ohne sich mit den Ausführungen im angefochtenen Entscheid zu dieser Frage auseinanderzusetzen, dann kommen sie ihrer Substantiierungspflicht nicht hinreichend nach (E. 2.1 hiervor). Und wenn sie eine Verletzung des Rechtsgleichheitsgebots rügen, indem einzelne Miteigentümer bauliche Massnahmen hätten vornehmen dürfen und sie nicht, dann verkennen sie, dass im angefochtenen Urteil die sachlichen Gründe für die unterschiedliche Behandlung dargelegt werden (zeitlicher Ablauf, Zustimmung der Miteigentümer) und zudem ausgeführt wird, die Beschwerdeführer hätten sich entgegen ihrer Verfahrenspflicht mit den übrigen Boxen vor der Erstinstanz nicht befasst. Die Beschwerdeführer setzen sich mit diesen Erwägungen nicht hinreichend substantiiert auseinander. Auch darauf kann nicht eingetreten werden.
2.3 Das Bezirksgericht hat im Weiteren festgehalten, aus der Expertise (pag. 274) sei ersichtlich, dass auf dem Abstellplatz A eine Leiter, ein Plastikstuhl, ein Tisch, Palletten sowie andere Utensilien lagerten. Die Beschwerdeführer wenden dagegen ein, diese Feststellung sei willkürlich, weil sie weder aktenkundig sei noch sich aus der Expertise ergebe. Zutreffend ist, dass sich diese Tatsachen nicht aus dem Textteil des Gutachtens ergeben (pag. 263 bis 269). Der Expertise sind nebst vier Plänen auch ein A4-Blatt mit sechs Fotos beigefügt (pag. S. 274), worauf - wenn auch schlecht - die vom Bezirksgericht genannten Gegenstände sichtbar sind. Mit der blossen Behauptung des Gegenteils kommen die Beschwerdeführer ihrer Begründungspflicht nicht nach. Im Übrigen könnte das Bundesgericht erst eingreifen, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein könnte (<ref-law>). Dazu fehlen Ausführungen in der Beschwerdeschrift. Die Erheblichkeit ist auch nicht ersichtlich, weil die Vorinstanz zusätzlich aufgrund von mehreren anderen Beweismitteln, deren Würdigung nicht als willkürlich gerügt wird, zum Schluss gelangt ist, der Autoabstellplatz werde als Lager / Depot genutzt. Auf die Rüge ist nicht einzutreten.
2.4 Im angefochtenen Urteil wird ferner bemerkt, die Beschwerdeführer liessen ausser Acht, dass die Miteigentümer, die ihre Abstellplätze mit Holzverschlägen abgeschlossen hätten, die dazu notwendige Zustimmung der Stockwerkeigentümer eingeholt hätten. Dazu bringen die Beschwerdeführer vor, diese Feststellung sei willkürlich, "da sich diese Feststellung nicht aus den ersichtlich ist". Auf diese unverständliche Rüge kann nicht eingetreten werden.
3. Nach dem Ausgeführten kann auf die Beschwerde in Zivilsachen wie auch auf die subsidiäre Verfassungsbeschwerde nicht eingetreten werden. Die Beschwerdeführer werden damit kostenpflichtig unter solidarischer Haftung (<ref-law>). Eine Parteientschädigung an die Beschwerdegegner entfällt, da sie nicht zur Vernehmlassung eingeladen worden sind (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde in Zivilsachen und die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 1'500.-- werden den Beschwerdeführern gemeinsam auferlegt.
3. Dieses Urteil wird den Parteien und dem Bezirksgericht Brig, Östlich-Raron und Goms, schriftlich mitgeteilt.
Lausanne, 25. August 2008
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Raselli Schett